Question

一道求最小生成树的OJ，很简单的算法基本题目，ZOJ 2326 Tangled in Cables，求大虾赐教，解决了加到80分

题目：
ZOJ 2326
我的答案，用的克鲁斯卡尔算法，不知道错哪里
#include<stdio.h>
#include<string.h>
char name[100][21],ch1[21],ch2[21]; //定义字符数组存储点的名字，ch1、ch2存储读取进来的点的名字
int m,boss[10000]; //定义点的数量m、根节点数组boss[];
struct journey //定义结构存储两个点的代表数字及距离
{
int x;
int y;
double distance;
};
int find_number(char ch[]) //用字符数组的行数作为代表数字，找出代表数字
{
int i;
for(i=0;i<m;i++)
if(strcmp(name[i],ch)==0)
break;
return i;
}
int find_boss(int n) //找出根节点
{
int temp,x=n;
while(boss[n]!=n)
n=boss[n];
while(x!=n) //压缩路径
{
temp=boss[x];
boss[x]=n;
x=temp;
}
return n;
}
int main()
{
double max,distance;
int i,j,n,x,y,min,sum;
struct journey k[10000],temp;
while(scanf("%lf",&max)!=EOF)
{
getchar();
distance=0; //初始化
sum=0;
scanf("%d",&m);
getchar();
for(i=0;i<m;i++) //读取名字
gets(name[i]);
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%s%s%lf",ch1,ch2,&k[i].distance); //结构存入距离
getchar();
k[i].x=find_number(ch1); //把字符串代表的数字存入结构中
k[i].y=find_number(ch2);
if(k[i].x>k[i].y) //调整顺序，方便压缩路径
k[i].x^=k[i].y^=k[i].x^=k[i].y;
}
for(i=0;i<n-1;i++) //以距离升序排列结构，克鲁斯卡尔算法第一步
{
min=i;
for(j=i+1;j<n;j++)
if(k[min].distance>k[j].distance)
min=j;
if(min!=i)
{
temp=k[min];
k[min]=k[i];
k[i]=temp;
}
}
for(i=0;i<m;i++) //各点以自己为根节点，完全孤立，克鲁斯卡尔算法第二步
boss[i]=i;
for(i=0;i<n;i++)
{
x=find_boss(k[i].x); //找出结构中两个点的根节点
y=find_boss(k[i].y);
if(x!=y) //若x不等于y，说明属于两个不同的集合
{
boss[x]=y; //合并集合
distance=distance+k[i].distance; //统计距离
sum++; //记录已加入边数
if(sum==m-1) //如果边数足够，结束
break;
}
}
if(distance>max) //输出
printf("Not enough cable\n");
else
printf("Need %.1f miles of cable\n",distance);
}
return 0;
}

改动了很多次还是WR，哪位大虾能帮忙找出错在哪？解决了加到80分。

Answer 1

把数组开大就OK