http://poj.org/problem?id=3723
http://blog.csdn.net/chenguolinblog/article/details/8043046
1 首先我们应该区分开男孩和女孩，只要将男孩的编号加上女孩的个数n，这样就可以做到男孩和女孩的编号是不同的。
2 题目中说了如果两个人有关系，并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题，那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面，每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最小生成树相加，然后在加上s*10000（没有关系的时候选择一个人要10000），即为最后的答案。
Also check http://www.acmerblog.com/POJ-3723-Conscription-blog-1136.html
Read full article from 3723 -- Conscription
Description
Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl x and boy y have a relationship d and one of them has been collected, Windy can collect the other one with 10000-d RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.
Input
The first line of input is the number of test case.
The first line of each test case contains three integers, N, M and R.
Then R lines followed, each contains three integers xi, yi and di.
There is a blank line before each test case.
1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 10000
The first line of each test case contains three integers, N, M and R.
Then R lines followed, each contains three integers xi, yi and di.
There is a blank line before each test case.
1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 10000
Output
For each test case output the answer in a single line.
Sample Input
1 5 5 8 4 3 6831 1 3 4583 0 0 6592 0 1 3063 3 3 4975 1 3 2049 4 2 2104 2 2 781
Sample Output
71071
题意：需要招募女兵N人，男兵M人。每征募一人需要$10000。但是如果两个人之间（已征募与要被征募）有关系，就可以依据亲密度大小减免花费，此时花费等于10000-已经征募的人中与ta的最大亲密度。求花费最少的招募顺序。
题解：是一个无向图，并且可以得知这是一个森林，所以可以把人看做点，关系是边权，就转换为求最大权森林。将边权取反，采用kruskal（因为可能有圈）。
http://tech.artyoo.me/?p=60
男生女生是图中相同类型的点，只不过只有男生和女生之间才有路连通。所以用krusical来做，每次取最小值加入。和最小生成树一模一样
最后解答的那个序列，对应了原图各个连通分量上所有的生成树（若原图本身是一个连通图，那么解答序列对应了该连通图的一颗生成树）。但无论如何，最后在原图各个连通分量上生成的，必定是一颗树，而不含有圈。若有圈，则会产生矛盾。原图的边的权重，代表了男女之间的亲密度，其实也代表了招募该对男女可以减少的费用：原本招募一男一女需要10000*2=20000RMB，而若他们之间的亲密度为d，则在先招募其中一人后，再招募其中另一人则可减少d的费用，因此招募此二人的总费用实际为（10000*2-d）RMB。因此，此题实则可以转化为：在原图上找最大生成森林（若原图为连通图，则为找原图的最大生成树），这最大生成森林（或最大生成树）的总权值，其实代表了可以减少的费用，计为P；则最后的最小总费用就是10000*(N+M)-P。求最大生成森林，自然可以转换为求最小生成森林（树），其技巧是将所有边上的权值取负，则最后对应的最小生成森林（树）的总权值P'就是P的相反数，此时最后的最小总费用就是10000*(N+M)+P'。
int par[maxn];//并查集父亲
22 int hrank[maxn];//并查集树的高度
23 int x[maxn],y[maxn],d[maxn];
24 struct edge{
25 int u,v,cost;
26 };
27 edge es[maxn];
28 int V,E;
29 void init(int n)
30 {
31 for (int i=0; i<n; i++) {
32 par[i]=i;
33 hrank[i]=0;
34 }
35 }
36
37 int find(int x)
38 {
39 if (par[x]==x) {
40 return x;
41 }
42 else {
43 return par[x]=find(par[x]);
44 }
45 }
46
47 void unite(int x,int y)
48 {
49 x=find(x);
50 y=find(y);
51 if (x==y) {
52 return;
53 }
54 if (hrank[x]<hrank[y]) {
55 par[x]=y;
56 }
57 else {
58 par[y]=x;
59 if (hrank[x]==hrank[y]) {
60 hrank[x]++;
61 }
62 }
63 }
64
65 bool same(int x,int y)
66 {
67 return find(x)==find(y);
68 }
69
70 bool cmp(const edge& e1,const edge& e2)
71 {
72 return e1.cost<e2.cost;
73 }
74
75 int kruskal()
76 {
77 sort(es, es+E, cmp);
78 init(V);
79 int res=0;
80 for (int i=0; i<E; i++) {
81 edge e=es[i];
82 if (!same(e.u,e.v)) {
83 unite(e.u, e.v);
84 res+=e.cost;
85 }
86 }
87 return res;
88 }
89
90 int main()
91 {
94 int n;
95 int N,M,R;
96 scanf("%d",&n);
97 for (int i=0; i<n; i++) {
98 scanf("%d%d%d",&N,&M,&R);
99 V=N+M;
100 E=R;
101 for (int j=0; j<R; j++) {
102 scanf("%d%d%d",&x[j],&y[j],&d[j]);
103 es[j]=(edge){x[j],N+y[j],-d[j]};//N+y[j]……
104 }
105 printf("%d\n",10000*(N+M)+kruskal());
107 }
108
109 return 0;
110 }
http://tech.artyoo.me/?p=60
struct edge { int u, v, cost;};int testcase, testcase_id;int N, M, R;int x[MAX_N], y[MAX_N], d[MAX_R];struct edge es[MAX_R];//并查集数据 int parent[MAX_N * 2];bool cmp(const edge& e1, const edge& e2) { return e1.cost < e2.cost;}int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x]));}int kruskal() { sort(es, es + R, cmp); for(int i = 0; i < N + M; i++) parent[i] = i; int ans = 0; for(int i = 0; i < R; i++) { edge e = es[i]; int x = find(e.u); int y = find(e.v); if(x != y) { ans += e.cost; parent[x] = y; } } return ans;}int main() { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); scanf("%d\n", &testcase); for(testcase_id = 0; testcase_id < testcase; testcase_id++) { scanf("%d %d %d\n", &N, &M, &R); for(int i = 0; i < R; i++) { scanf("%d %d %d\n", &x[i], &y[i], &d[i]); es[i] = (edge){x[i], N + y[i], -d[i]}; } printf("%d\n", 10000 * (N + M) + kruskal()); } return 0; }1 首先我们应该区分开男孩和女孩，只要将男孩的编号加上女孩的个数n，这样就可以做到男孩和女孩的编号是不同的。
2 题目中说了如果两个人有关系，并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题，那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面，每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最小生成树相加，然后在加上s*10000（没有关系的时候选择一个人要10000），即为最后的答案。
void kruskal(){
int ans = 0;
sort(e , e+r , cmp);
/*求出s个集合的最小生成树的和*/
for(int i = 0 ; i < r ; i++){
int root_x = find_Set(e[i].x);
int root_y = find_Set(e[i].y);
if(root_x != root_y){
ans += e[i].value;
union_Set(root_x , root_y);
}
}
/*求有几个集合*/
int cnt = 0;
int vis[MAXN];
memset(vis , 0 , sizeof(vis));
for(int i = 0 ; i < n+m ; i++){
int tmp = find_Set(i);
if(!vis[tmp]){
cnt++;
vis[tmp] = 1;
}
}
printf("%d\n" , ans+10000*cnt);
}
int main(){
int a , b , v;
scanf("%d" , &t);
while(t--){
scanf("%d%d%d" , &n , &m , &r);
init_Set();
for(int i = 0 ; i < r ; i++){
scanf("%d%d%d" , &a , &b , &v);
e[i].x = a;
e[i].y = b+n;
e[i].value = 10000-v;/*边的权值*/
}
kruskal();
}
return 0;
}
http://www.itwendao.com/article/detail/293915.htmlAlso check http://www.acmerblog.com/POJ-3723-Conscription-blog-1136.html
Read full article from 3723 -- Conscription
