HDU 1863 通畅工程（kruskal算法）

HDU 1863 畅通工程（kruskal算法）

转载请注明出处：http://blog.****.net/a1dark

分析：还是一道水水的最小生成树、改了一点条件而已、代码基本不变、继续水、

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
    int s,e;
    int val;
}flag[150];
int map[150];
int n,m,temp;
int cmp(node a,node b){
    if(a.val<b.val)
        return 1;
    else return 0;
}
void init(){
    for(int i=1;i<=m;i++)
        map[i]=i;
}
int find(int x){
    int r=x;
    while(r!=map[r])
        r=map[r];
    int b=x;
    int f;
    while(b!=r){
        f=map[b];
        map[b]=r;
        b=f;
    }
    return r;
}
int merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy){
        map[fx]=fy;
        temp--;
        return 1;
    }
    return 0;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0)break;
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&flag[i].s,&flag[i].e,&flag[i].val);
        }
        sort(flag,flag+n,cmp);
        int sum=0,ans=0;
        temp=m-1;
        init();
        for(int i=0;i<n;i++){
            ans=merge(flag[i].s,flag[i].e);
            if(ans)
                sum+=flag[i].val;
        }
        if(temp>0)
            printf("?\n");
        else
            printf("%d\n",sum);
    }
    return 0;
}