题解 | #继续畅通工程#

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

struct Line {
    int start;
    int end;
    int price;
    int state;

};
bool cmp(Line*& left, Line*& right) {
    if (left->state != right->state) {
        return left->state > right->state;
    } else {
        return left->price < right->price;
    }
}
int Father[100];

int Find(int a) {
    if (a != Father[a]) {
        Father[a] = Find(Father[a]);
    }
    return Father[a];
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        //初始化并查集
        for (int i = 0; i <= n; i++) {
            Father[i] = i;
        }
        int weight = 0; //修路花费；
        vector<Line*> myLine;
        for (int i = 1; i <= (n * (n - 1)) / 2; ++i) {//把所有道路加入数组
            Line* node = new Line;
            cin >> node->start >> node->end >> node->price >> node->state;
            myLine.push_back(node);
        }
        //排序
        sort(myLine.begin(), myLine.end(), cmp);
        //查找最优路线
        for (vector<Line*>::iterator it = myLine.begin(); it != myLine.end(); ++it) {
            int start = Find((*it)->start);
            int end = Find((*it)->end);
            if (start != end) {
                Father[end] = start;
                if (0 == (*it)->state) {
                    weight += (*it)->price;
                }
            }

        }
        printf("%d\n", weight);
    }
}