用的Kruskal算法，没用并查集而是在结构体里多了一个变量判断是否是一个连通量。
结果wrong answer。
#include
#include
using namespace std;
struct in{
int f,n,price;
};
int main()
{
int m=1,are[10000],root=1,i;
while(m!=0)
{
int total=0,head=1,tail=1,q[1000]={0},mark=1;
in r[2000];
int j,k,z,h,g,x,flag=1,s;
char c,d;
total=0;
scanf("%d",&m);
if(m==0) break;
for(i=1;i<=m-1;i++)
{
scanf("\n%c",&c);
z=c-'A'+1;
scanf("%d",&g);
for(j=1;j<=g;j++)
{
scanf("\n%c%d",&d,&k);
h=d-'A'+1;
r[flag].price=k;
r[flag].f=z;
r[flag].n=h;
flag++;
}
}
flag--;
for(i=1;i<=flag;i++) //排序；
for(j=1;j<=flag-i;j++)
{
if(r[j].price>r[j+1].price)
{
r[j].price=r[j].price+r[j+1].price;
r[j+1].price=r[j].price-r[j+1].price;
r[j].price=r[j].price-r[j+1].price;
r[j].f=r[j].f+r[j+1].f;
r[j+1].f=r[j].f-r[j+1].f;
r[j].f=r[j].f-r[j+1].f;
r[j].n=r[j].n+r[j+1].n;
r[j+1].n=r[j].n-r[j+1].n;
r[j].n=r[j].n-r[j+1].n;
}
}
for(i=1;i<=flag;i++)
{ //判断是否是一个连通分量
if(q[r[i].n]==0&&q[r[i].f]==0)
{
total=total+r[i].price;
q[r[i].n]=mark;
q[r[i].f]=mark;
mark++;
continue;
}
if(q[r[i].n]!=q[r[i].f])
{
total=total+r[i].price;
if(q[r[i].n]==0)
{
q[r[i].n]=q[r[i].f];
}
else if(q[r[i].f]==0)
{
q[r[i].f]=q[r[i].n];
}
else if(q[r[i].n]!=0&&q[r[i].f]!=0)
{
for(j=1;j<=26;j++)
{
if(q[j]==q[r[i].f])
q[j]=q[r[i].n];
}
}
}
}
are[root]=total;
root++;
}
root--;
for(i=1;i<=root;i++)
{
printf("%d",are[i]);
if(i<root) printf("\n");
}
}
