题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1879
最小生成树，只要注意先把已经修好的路先合并了
//prim算法模版 只要改变一点点就可以了
//开始使用cin输入，结果TLE了
#include <iostream>
#include <algorithm>
using namespace std;
struct Road {
int c1, c2, cost, isbuilt;
};
Road road[5051];
int city[101];
int cmp (const Road a, const Road b)
{
return a.cost < b.cost;
}
int Find(const int n)
{
if (city[n] == -1)
return n;
return city[n] = Find(city[n]);
}
int Merge(const int a, const int b)
{
int x = Find(a);
int y = Find(b);
if (x == y) return 0;
if (x < y) city[y] = x;
else city[x] = y;
return 1;
}
int main()
{
int n, m;
int sum, count, i;
while (scanf("%d", &n) && n) {
m = n*(n-1)/2;
memset(city, -1, sizeof(city));
sum = count = 0;
for (i = 0; i < m; i++) {
scanf("%d%d%d%d", &road[i].c1, &road[i].c2, &road[i].cost, &road[i].isbuilt);
if (road[i].isbuilt) {
if(Merge(road[i].c1, road[i].c2))
count ++;
}
}
sort(road, road+m, cmp);
for (i = 0; i < m; i++) {
if (count == n-1) break;
if (!road[i].isbuilt && Merge(road[i].c1, road[i].c2)) {
sum += road[i].cost;
count ++;
}
}
cout << sum << endl;
}
return 0;
}