题解 | #继续畅通工程#

求最小生成树，如果一条路已经修好，将其w置为0

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 110;
int p[N];
int n;

void init() {
    for (int i = 0; i <= n; i++) p[i] = i;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void un(int u, int v) {
    int root1 = find(u), root2 = find(v);
    if (root1 != root2) p[root1] = root2;
}

struct edge {
    int u, v, w;
    edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};

vector<edge> es;
int sum = 0;

bool cmp(edge e1, edge e2) {
    if (e1.w < e2.w) return true;
    return false;
}

void kruskal() {
    sort(es.begin(), es.end(), cmp);

    int cnt = 0;
    for (auto x : es) {
        int root1 = find(x.u), root2 = find(x.v);
        if (root1 == root2) continue;
        cnt++;
        sum += x.w;
        un(root1, root2);
        if (cnt == n - 1) {
            break;
        }
    }

    cout << sum << endl;
}

int main() {

    while (cin >> n) {
        if(n == 0) break;
        init();
        es.clear();
        sum = 0;
        int u, v, w, op;
        for (int i = 0; i < n * (n - 1) / 2; i++) {
            cin >> u >> v >> w >> op;
            if (op == 1) w = 0;
            es.push_back({u, v, w});
        }

        kruskal();
    }

    return 0;
}