UVA 1664 Conquer a New Region——并查集

UVA 1664 Conquer a New Region——并查集

老套路，每个点维护一个sum和cnt，表示以这个点为父节点的子树的最大容量和以及节点的数量，然后每条边从大到小排序，遍历，假设当前边两节点是u，v，那么先通过并查集找出两节点的父节点x，y，然后根据sum【x】+cost（当前边的边权）*cnt【y】以及sum【y】+cost*cnt【x】的大小进行更新

#include #include #include #include using namespace std;const int maxn = 2e5+10;int par[maxn];void init(int n) { for (int i = 0; i <= n; i++) par[i] = i;}int query(int x) { return par[x] == x ? x : par[x] = query(par[x]);}int n;struct Edge { int u, v, cost; bool operator < (const Edge &e) const { return cost > e.cost; }}edge[maxn];long long ans, sum[maxn], cnt[maxn];int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n-1; i++) scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].cost); sort(edge, edge+n-1); init(n); ans = 0; memset(sum, 0, sizeof(sum)); for (int i = 0; i <= n; i++) cnt[i] = 1; for (int i = 0; i < n-1; i++) { int x = query(edge[i].u), y = query(edge[i].v); long long cost = edge[i].cost; long long t1 = sum[x] + cost * cnt[y], t2 = sum[y] + cost * cnt[x]; if (t1 > t2) { par[y] = x; sum[x] = t1; cnt[x] += cnt[y]; } else { par[x] = y; sum[y] = t2; cnt[y] += cnt[x]; } } for (int i = 1; i <= n; i++) ans = max(ans, sum[i]); cout << ans << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。