题目链接：http://code.hdu.edu.cn/showproblem.php?pid=1879
这条题目我的做法与解决Constructing Roads的解法是相同的。
0 表示没有连通；1代表已连通。在已连通村庄的道路的基础上，找到扩展出来的最小生成树。
#include <iostream>
#include <algorithm>
using namespace std; const int maxe = + ;
int rep[maxe], vis[maxe]; struct sets
{
int v1, v2;
int value;
} exa[maxe]; int cmp(sets a, sets b)
{
return a.value < b.value;
} int find(int x)
{
return x == rep[x] ? x : find(rep[x]);
} int main()
{
int i, n, a, b, c, x, y, cnt, flag, sign;
while (scanf("%d", &n) != EOF && n)
{
for (i = ; i <= n; i++)
rep[i] = i;
cnt = flag = ;
n *= (n-)/;
memset(vis, , sizeof(vis));
for (i = ; i < n; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &sign);
if (a > b)
swap(a, b);
if (sign == )
{
exa[cnt].v1 = a;
exa[cnt].v2 = b;
exa[cnt].value = c;
cnt++;
}
else
{
x = find(a);
y = find(b);
if (x > y)
swap(x, y);
if (vis[a] && vis[b])
rep[x] = y;
else
{
if (x == y)
flag = ;
if (!vis[a] && !vis[b])
{
rep[x] = y;
vis[a] = vis[b] = ;
}
else if (!vis[a])
{
rep[x] = y;
vis[a] = ;
}
else if (!vis[b])
{
rep[x] = y;
vis[b] = ;
}
}
}
}
sort(exa, exa+cnt, cmp);
if (!flag)
{
int minval = ;
for (i = ; i < cnt; i++)
{
x = find(exa[i].v1);
y = find(exa[i].v2);
if (x != y)
{
minval += exa[i].value;
if (x < y)
rep[x] = y;
else
rep[y] = x;
}
}
printf("%d\n", minval);
}
else
printf("0\n");
}
return ;
}