poj 3723 Conscription

点击打开链接poj 3723

思路：kruskal + 最小生成树

分析：
1 首先我们应该区分开男孩和女孩，只要将男孩的编号加上女孩的个数n，这样就可以做到男孩和女孩的编号是不同的。
2 题目中说了如果两个人有关系，并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题，那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面，每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最小生成树相加，然后在加上s*10000（没有关系的时候选择一个人要10000），即为最后的答案。


代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 50010

int t , n , m , r;
int father[MAXN];
int rank[MAXN];
struct Edge{
    int x;
    int y;
    int value;
}e[MAXN];

void init_Set(){
    memset(rank , 0 , sizeof(rank));
    for(int i = 0 ; i <= n+m ; i++)
       father[i] = i;
}

int find_Set(int x){
    if(x != father[x])
      father[x] = find_Set(father[x]);
    return father[x];
}

void union_Set(int x , int y){
    if(rank[x] > rank[y])
      father[y] = x;
    else{
      if(rank[x] == rank[y])
        rank[y]++;
      father[x] = y;
    }
}

bool cmp(Edge e1 , Edge e2){
     return e1.value < e2.value;
}

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;
}