HDU1879 继续畅通工程（最小生成树）

题目链接

MST，已经有路的权值设为 0 就可以。

Kruskal 搞的。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;
const int MAXM = 10000;
int F[MAXN];
struct Edge{
    int u, v, w;
}edge[MAXM];
int tol;
void addedge(int u,int v,int w){
    edge[tol].u = u;
    edge[tol].v = v;
    edge[tol++].w = w;
}
bool cmp(Edge a,Edge b){
    return a.w < b.w;
}
int findfa(int x){
    if(F[x] == -1)return x;
    else return F[x] = findfa(F[x]);
}
int Kruskal(int n){
    memset(F, -1, sizeof(F));
    sort(edge, edge+tol, cmp);
    int cnt = 0;
    int ans = 0;
    for(int i = 0; i < tol; i++){
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        int t1 = findfa(u);
        int t2 = findfa(v);
        if(t1 != t2){
            ans += w;
            F[t1] = t2;
            cnt++;
        }
        if(cnt == n-1)break;
}
    if(cnt < n-1)return -1;
    else return ans;
}


int main(){
//    freopen("a.txt", "r", stdin);
    int n;
    while(~scanf("%d", &n) && n){
        int k = n*(n-1)/2;
        for(tol = 0; tol < k; ){
            int a, b, c, d;
            scanf("%d %d %d %d", &a, &b, &c, &d);
            if(d) c = 0;
            addedge(a, b, c);
        }
        cout << Kruskal(n) << endl;
    }
    return 0;
}