HDU1879 继续畅通工程

题目链接。

分析：

水.

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100
#define MAXM 6000

int p[MAXN], cnt, ans;

int find(int x){return p[x] == x ? x : (p[x]=find(p[x]));}

struct node{
    int u, v, w, flag;
}edge[MAXM];

int cmp(struct node *a, struct node *b){
    return (*a).w - (*b).w;
}

int Union(int x, int y){
    x = find(x); y = find(y);
    if(x != y){
        p[x] = y;
        return 1;
    }
    else return 0;
}

void Kruskal(int n, int m){
    int i;
    qsort(edge, m, sizeof(edge[0]), cmp);
    for(i=0; i<m; i++){
        if(!edge[i].flag){
            if(Union(edge[i].u, edge[i].v)){
                cnt++;
                ans += edge[i].w;
                if(cnt == n-1) return;
            }
        }
    }
}

int main(){
    int n, m, i;
    while(scanf("%d", &n) == 1 && n){
        m = n*(n-1)/2;
        cnt = ans = 0;
        for(i=1; i<=n; i++) p[i] = i;
        for(i=0; i<m; i++){
            scanf("%d %d %d %d", &edge[i].u, &edge[i].v, &edge[i].w, &edge[i].flag);
            if(edge[i].flag){
                if(Union(edge[i].u, edge[i].v)) cnt++;
            }
        }
        Kruskal(n, m);
        printf("%d\n", ans);
    }

    return 0;
}