您所在位置：主题：zoj 2326遇到问题寻求帮助！！（最小生成树问题）
zdin
[专家分：0] 发布于 2011-10-22 17:03:00
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 310
#define M 1000000
double size;
int n,m,pre[N],count;
char ch1[25],ch2[25];
char a[N][25];
typedef struct
{
int i,j;
double len;
}node;
node city[M];
int cmp(const void *a,const void *b)
{
return ((node*)a)->len-((node*)b)->len;
}
int find(int x)
{
while(x!=pre[x])
x=pre[x];
return x;
}
void kruskal()
{
double sum=0;
int i,a,b;
qsort(city,count,sizeof(node),cmp);
for(i=0;i<count;i++)
{
a=find(city[i].i);
b=find(city[i].j);
if(a!=b)
{
sum+=city[i].len;
pre[b]=a;
}
}
if(sum>size)
printf("Not enough cable\n");
else
printf("Need %.1lf miles of cable\n",sum);
}
int main()
{
int i,j;
scanf("%lf",&size);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",a[i]);
pre[i]=i;
}
scanf("%d",&m);
count=0;
for(i=0;i<m;i++)
{
scanf("%s %s %lf",ch1,ch2,&city[count].len);
for(j=0;j<n;j++)
{
if(strcmp(ch1,a[j])==0)
city[count].i=j;
if(strcmp(ch2,a[j])==0)
city[count].j=j;
}
count++;
}
kruskal();
return 0;
}
以上是我写的kruskal算法解这道题的代码，但一直就是错误的，纠结了一天了都；之前还做了一题与该题情形类似：都是prim算法的给过了，但是kruskal的就是过不了。我想应该是我对这个算法哪里理解有偏差了吧，望请各位能指点下在下。。先谢了 [em2]
这是我自一次发帖，是否分错类还是放错板块什么的希望管理员千万给过了吧， 以后一定注意。。
#include<stdlib.h>
#include<string.h>
#define N 310
#define M 1000000
double size;
int n,m,pre[N],count;
char ch1[25],ch2[25];
char a[N][25];
typedef struct
{
int i,j;
double len;
}node;
node city[M];
int cmp(const void *a,const void *b)
{
return ((node*)a)->len-((node*)b)->len;
}
int find(int x)
{
while(x!=pre[x])
x=pre[x];
return x;
}
void kruskal()
{
double sum=0;
int i,a,b;
qsort(city,count,sizeof(node),cmp);
for(i=0;i<count;i++)
{
a=find(city[i].i);
b=find(city[i].j);
if(a!=b)
{
sum+=city[i].len;
pre[b]=a;
}
}
if(sum>size)
printf("Not enough cable\n");
else
printf("Need %.1lf miles of cable\n",sum);
}
int main()
{
int i,j;
scanf("%lf",&size);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",a[i]);
pre[i]=i;
}
scanf("%d",&m);
count=0;
for(i=0;i<m;i++)
{
scanf("%s %s %lf",ch1,ch2,&city[count].len);
for(j=0;j<n;j++)
{
if(strcmp(ch1,a[j])==0)
city[count].i=j;
if(strcmp(ch2,a[j])==0)
city[count].j=j;
}
count++;
}
kruskal();
return 0;
}
以上是我写的kruskal算法解这道题的代码，但一直就是错误的，纠结了一天了都；之前还做了一题与该题情形类似：都是prim算法的给过了，但是kruskal的就是过不了。我想应该是我对这个算法哪里理解有偏差了吧，望请各位能指点下在下。。先谢了 [em2]
这是我自一次发帖，是否分错类还是放错板块什么的希望管理员千万给过了吧， 以后一定注意。。
