链接：http://acm.hdu.edu.cn/showproblem.php?pid=1879
并查集+优先队列...用cin会超时...TLE了好几次
#include <iostream>
#include<queue>
#include<cstdio>
#define MAX_N 105
using namespace std;
class rode
{
public:
int from;
int to;
int cost;
int sign;
};
int par[MAX_N];
int high[MAX_N];
int c; //记录当前有几个集合
bool operator <(rode a,rode b)
{
return a.cost>b.cost;
}
priority_queue <rode> data;
void init(int n) //初始化
{
c=n;
for(int i=1;i<=n;i++)
{
par[i]=i;
high[i]=0;
}
}
int ifind(int x)
{
if(par[x]==x)
return x;
else
return par[x]=ifind(par[x]);
}
void unite(int x,int y)
{
x=ifind(x);
y=ifind(y);
if(x==y)
return;
if(high[x]<high[y])
par[x]=y;
else
{
par[y]=x;
if(high[x]==high[y])
high[x]++;
}
c--;
}
bool same (int x,int y)
{
return ifind(x)==ifind(y);
}
void readrode(int n)
{
rode t;
while(!data.empty())
data.pop();
for(int i=0; i<n*(n-1)/2; i++)
{
scanf("%d%d%d%d",&t.from,&t.to,&t.cost,&t.sign);
if(t.sign) //如果路已修好
unite(t.from,t.to);
else //未修好，则加入队列
data.push(t);
}
}
int markrode(void)
{
int sum=0;
rode t;
while(!data.empty()&&c>1)
{
t=data.top();
data.pop();
if(!same(t.from,t.to))
{
unite(t.from,t.to);
sum+=t.cost;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
init(n);
readrode(n);
cout<<markrode()<<endl;
}
return 0;
}