poj 2377 Bad Cowtractors

点击打开链接poj 2377

思路：最先生成树+kruskal

分析：kruskal的模板题，最后只要加上一个判断是否所有的点的根节点都是一样的即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
#define INF 0XFFFFFFF

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

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

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

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

void kruskal(){
     init_Set();
     sort(e , e+m , cmp);
     ans = 0;
     for(int i = 0 ; i < m ; i++){
        int root_x = find_Set(e[i].x);
        int root_y = find_Set(e[i].y);
        if(root_x != root_y){
          union_Set(root_x , root_y);
          ans += e[i].value;
        } 
     }
     int cnt = 0;
     int vis[20010];
     memset(vis , 0 , sizeof(vis));
     for(int i = 1 ; i <= n ; i++){ 
        if(!vis[find_Set(i)]){
           cnt++;
           vis[find_Set(i)] = 1;
        }
     }
     if(cnt == 1)
         printf("%d\n" , ans);
     else
         printf("-1\n");
}

int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i < m ; i++)
        scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
    kruskal();
    return 0;
}