「CH6201」走廊泼水节

传送门

考虑 \(\text{Kruskal}\) 的过程以及用到一个最小生成树的性质即可。

在联通两个联通块时，我们肯定会选择最小的一条边来连接这两个联通块，那么这两个联通块之间的其他边都必须比这条边长，不然最小生成树就不唯一。

又为了让答案最小化，我们就只需要让这些其他边比当前边多 \(1\) 就好了。

参考代码：

#include <algorithm>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 6010;

typedef long long LL;

int n, Fa[_], siz[_];

struct node { int x, y, z; } t[_];

inline bool cmp(const node& a, const node& b) { return a.z < b.z; }

inline int Find(int x) { return Fa[x] == x ? x : Fa[x] = Find(Fa[x]); }

inline void solve() {

	read(n);

	for (rg int i = 1; i <= n; ++i) Fa[i] = i, siz[i] = 1;

	for (rg int x, y, z, i = 1; i < n; ++i)

		read(x), read(y), read(z), t[i] = (node) { x, y, z };

	sort(t + 1, t + n, cmp);

	LL ans = 0;

	for (rg int i = 1; i < n; ++i) {

		int x = Find(t[i].x), y = Find(t[i].y);

		if (x == y) continue;

		ans += 1ll * (t[i].z + 1) * (siz[x] * siz[y] - 1);

		Fa[x] = y, siz[y] += siz[x];

	}

	printf("%lld\n", ans);

}

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	int T; read(T);

	while (T--) solve();

	return 0;

}

巴特西

「CH6201」走廊泼水节

「CH6201」走廊泼水节

最新文章

热门文章