POJ-3723 Conscription---最大权森林---最小生成树

题目链接：

题目大意：

需要征募女兵N人, 男兵M人. 每征募一个人需要花费10000美元. 带式如果已经征募的人中有一些关系亲密的人, 那么可以少花一些钱. 给出若干的男女之前的1~9999指尖的亲密关系,征募某个人的费用是10000-(已经招募的人中和自己的亲密度最的最大值). 要求通过适当的征募顺序使得征募所有人所用的费用最小.

思路：

在征募某个人a时,如果使用来a和b之间的关系,那么就连一条a到b的边.假设这个图中存在圈,那么无论以什么顺序征募这个圈上的所有人, 都会产生矛盾.(只有男女关系是产生不了圈的…)因此可以直到这个图是一片森林. 反之,如果给了一片森林那么就可以使用对应的关系确定征募的顺序.
可以把人看作顶点, 关系看作边,这个问题就可以转化为求解无向图中的最大权森林问题.最大权森灵问题可以通过把所有边取反之后用最小生成树的算法求解.

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdio>
 7 using namespace std;
 8 typedef pair<int, int> Pair;
 9 const int maxn = 50000 + 10;
10 const int INF = 0x3f3f3f3f;
11 int T, n, m, n1, n2;
12 struct edge
13 {
14     int u, v, w;
15     edge(int v, int w):v(v), w(w){}
16     edge(){}
17     bool operator <(const edge a)const
18     {
19         return w < a.w;
20     }
21 };
22 edge e[maxn];
23 int p[maxn];
24 int Find(int x)
25 {
26     return x == p[x] ? x : p[x] = Find(p[x]);
27 }
28 void kruskal()
29 {
30     for(int i = 0; i <= n1 + n2; i++)p[i] = i;
31     sort(e, e + m);
32     int sum = 0;
33     for(int i = 0; i < m; i++)
34     {
35         int u = e[i].u, v = e[i].v, w = e[i].w;
36         int x = Find(u), y = Find(v);
37         if(x == y)continue;
38         sum += w;
39         p[x] = y;
40     }
41     int ans = (n1 + n2) * 10000 + sum;
42     cout<<ans<<endl;
43 }
44 int main()
45 {
46     cin >> T;
47     while(T--)
48     {
49         cin >> n1 >> n2 >> m;
50         for(int i = 0; i < m; i++)
51         {
52             scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
53             e[i].v += n1;//将女人标号移至男人后面
54             e[i].w = -e[i].w;//边取负数，求最小生成树，用总值减就得到最大森林权值
55         }
56         kruskal();
57     }
58 }