题解#Knights of the Old Republic#

题解：

这题的思路应该考虑利用kruskal的性质，即最小边若连着两个不相同的连通块，那么其他任意的边连接这两个连通块都不会优与这个最小边。

我们可以发现，通过这个性质去理解这题，可以使得连通块共享最小资源产武士的途径，也可以共享所有的武士数量。那么根据kruskal，我们要选择某条边，一定可以把之前所有的边都打通，使得之后的状态都更新到当前的状态下面。

代码：


///here is jmr's codes
///if you want to copy,please call me 29856325137
///thanks
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
double eps = 1e-6;
const int maxn = 1e6 + 5;
int n, m;
ll a[maxn], b[maxn];
struct node {
	ll a, b, v;
	bool operator<(const node& t)const {
		return t.v > v;
	}
}x[maxn];
int fa[maxn];
ll bin[maxn];
ll sum[maxn];
int findfa(int x) {
	if (x == fa[x]) {
		return x;
	}
	else return fa[x] = findfa(fa[x]);
}
int main() {

	ios::sync_with_stdio(0);
	cin >> n >> m;
	//ll a, b;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		fa[i] = i;
		sum[i] = a[i] * b[i];
		bin[i] = a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> x[i].a >> x[i].b >> x[i].v;
	}
	ll ans = 0;
	sort(x + 1, x + 1 + m);
	for (int i = 1; i <= m; i++) {
		int tt = findfa(x[i].a), rr = findfa(x[i].b);
		if(tt == rr)continue;
		ll mm = min(b[tt], b[rr]);
		ll nb = max(bin[tt], bin[rr]);
		nb = max(nb, x[i].v);
		sum[rr] = min(sum[rr] + sum[tt], nb * mm);
		fa[tt] = rr;
		bin[rr] = nb;
		b[rr] = mm;

	}
	//ll ans = 0;
	for (int i = 1; i <= n; i++)findfa(i);
	for (int i = 1; i <= n; i++) {
		if (i == fa[i])ans += sum[i];
	}
	cout << ans << "\n";





}

题解#Knights of the Old Republic#

tag:

题解：

代码：