以hdu1879为例,附上一份板子:hdu1879
//hdu1879
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e8;
int n;
int m;
struct Node {
int start;
int end;
int w;
}edge[maxn];
int pre[maxn];
int sum;
bool cmp(Node a, Node b)
{
return a.w < b.w;
}
int find(int x) {
if (x == pre[x])
return x;
return pre[x] = find(pre[x]);
}
void Kruscal(int x, int y, int n) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
pre[fx] = fy;
sum += edge[n].w;
}
}
int main()
{
while (cin >> n) {
if (n == 0)break;
int m = n*(n - 1) / 2;
for (int i = 0; i <= 110; i++)
pre[i] = i;
int u, v, w, flag;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w >> flag;
edge[i].start = u;
edge[i].end = v;
if (flag == 1)
edge[i].w = 0;
else
edge[i].w = w;
}
sort(edge + 1, edge + 1 + m, cmp);
sum = 0;
for (int i = 1; i <= m; i++) {//遍历所有的边,生成树
Kruscal(edge[i].start, edge[i].end, i);
}
cout << sum << endl;
}
return 0;
}