Contest1263/D.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 101;
int n;
struct Edge{
    int x,y,z;
    bool operator<(const Edge&that)const{
        return z < that.z;
    }
};
Edge edges[MAXN*MAXN];
int F[MAXN];
int getf(int x){
    if(x == F[x]){
        return F[x];
    }else{
        F[x] = getf(F[x]);
        return F[x];
    }
}
int Kruskal(){
    int cnt = 0, sum = 0;
    for(int i = 1; i <= n * ( n - 1) / 2; i++){
        int t1 = getf(edges[i].x);
        int t2 = getf(edges[i].y);
        if(t1 != t2){
            F[t2] = t1;
            cnt++;
            sum+=edges[i].z;
            if(cnt>=n-1){
                break;
            }
        }
    }
    if(cnt == n-1){
        return sum;
    }else{
        return -1;
    }
}
int main(){
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
    while(cin >> n ){
        if(n == 0)break;
        for(int i = 1; i <= n; i++){
            F[i] = i;//并查集初始化
        }
        for(int i = 1; i <= n * ( n - 1) / 2; i++){
            int x, y, z,flag;
            cin >> edges[i].x >> edges[i].y >> edges[i].z>>flag;//存边
            if (flag == 1)//这一步很关键，表示已经修好的路
                edges[i].z = 0;
        }
        sort(edges+1, edges+n * ( n - 1) / 2+1);
        int sum = Kruskal();
        cout << sum << endl;
    }
}