POJ 3723 Conscription （求最大权森林，kruskal，并查集）

本文主要是介绍POJ 3723 Conscription （求最大权森林，kruskal，并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 22222; //男兵和女兵总数
const int MAX_E = 55555; 
int f[MAX_N];
int h[MAX_N]; //记录树的高度避免退化
int N, M, R;void init(int n)  {int i;for(i = 0; i < n; i++) {f[i] = i;h[i] = 0;}
}int find(int x) {if(f[x] == x) return x;else return f[x] = find(f[x]);
}void unite(int x, int y) {x = find(x);y = find(y);if(x != y) {if(h[x] < h[y]) f[x] = y;else {f[y] = x;if(h[x] == h[y]) h[x]++;  //高度变化 }}
}
bool same(int x, int y) {return find(x) == find(y);
}struct edge{int from, to, cost;
};bool cmp(edge a, edge b) {return a.cost < b.cost;
}edge es[MAX_E];int kruskal() {sort(es, es + R, cmp);init(N + M);int res = 0;int i;for(i = 0; i < R; i++) {edge e = es[i];if(!same(e.from, e.to)) {unite(e.from, e.to);res += e.cost;}}return res;
}int main() {int t;scanf("%d", &t);while(t--) {scanf("%d %d %d", &N, &M, &R);int i;int x, y, z;for(i = 0; i < R; i++) {scanf("%d %d %d", &x, &y, &z);z = -z; //转换为求最小权森林 es[i].from = x, es[i].to = y + N, es[i].cost = z;  //注意对节点重新编号 }printf("%d\n", 10000 * (N + M) + kruskal());}return 0;
}

图有可能不联通，关键是理解题意，用没优惠之前的价格减去最大生成树即可得到答案。
参考博客： http://blog.csdn.net/y990041769/article/details/41773699
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack> 
#include <cstring>
#define eps 1e-8
using namespace std; 
int N, M, R;
int u[50010], v[50010], w[50010];
int p[50010], father[50010];
bool cmp(int a, int b) {return w[a] > w[b];
}
int find(int x)  
{  if(father[x]==x)  return x;  return father[x] = find(father[x]);  	//压缩路径 
} 
int kruskal() {int i;int sumd = 0;for(i = 0; i < R; i++) p[i] = i;for(i = 0; i < N + M; i++) father[i] = i;sort(p, p + R, cmp);for(i = 0; i < R; i++) {int e = p[i];int x = find(u[e]);int y = find(v[e]);if(x != y) {sumd += w[e];father[x] = y;}}return sumd;
}
int main() {int T;scanf("%d", &T);while(T--) {scanf("%d %d %d", &N, &M, &R);int i;int x;for(i = 0; i < R; i++) {scanf("%d %d %d", &u[i], &x, &w[i]);    //给每个点重新编号v[i] = N + x;}int sumd = kruskal();printf("%d\n", (M + N) * 10000 - sumd);}return 0;
}

这篇关于POJ 3723 Conscription （求最大权森林，kruskal，并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！