http://acm.hdu.edu.cn/showproblem.php?pid=1879
#include<iostream>//2243673 2010-03-24 20:56:41 Accepted 1879 375MS 320K 1070 B C++ 悔惜晟
#include<algorithm>//修改了三次终于AC， 为何就是代码的效率不高
#include<cstdio>
#include<cmath>
using namespace std;
int s[4991];
struct stu
{
int x;
int y;
int dis;
}df[4991];//开始这里定义4591 也不知你是怎么算
int cmp(stu a, stu b)
{
return a.dis < b.dis;
}
int find(int a)
{
int r = a;
while(r != s[r])
r = s[r];
return r;
}
void merge(int a, int b)
{
if(a > b)
s[b] = a;
else
s[a] = b;
}
int main()
{
int n, a, b, c, d, sum, m;
while(scanf("%d", &n)!=EOF && n!=0)
{
m = n*(n -1)/2;//这里以开始也错了n = 3 导致你错的
for(int i =0; i < m ; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
if(d == 0)
{
df[i].x = a;
df[i].y = b;
df[i].dis = c;
}
else
{
df[i].x = a;
df[i].y = b;
df[i].dis = 0;
}
}
sort(df, df + m, cmp);
for(int i = 1; i <= n*(n-1)/2; i++)
s[i]=i;
sum =0;
for(int i =0 ;i <n*(n-1)/2 ;i++)
{
int a = find(df[i].x);
int b = find(df[i].y);
if( a != b)
{
sum +=df[i].dis;
merge(a, b);
}
}
printf("%d/n",sum);
}
}