Question

hdu 1233测试实例过了，为什么提交老是wrong answer 呢？

以下是代码，哪位大牛帮忙看看,多谢啦！

#include<stdio.h>
#include<stdlib.h>
#define N 105
#define MAX 50005
typedef struct{
int x,y,cost;
}edge;
edge s[MAX];
int ans,f[N],rank[N];
int cmp(const void *a,const void *b)
{
return ((edge *)a)->cost-((edge *)b)->cost;
}
void make_set(int x)
{
f[x]=x;
rank[x]=0;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void Union(int x,int y,int cost)
{
ans+=cost;
if(rank[x]>rank[y])
f[y]=x;
else
{
if(rank[x]==rank[y])
rank[y]++;
f[x]=y;
}
}
int main()
{
int i,n,k,x,y;
while(scanf("%d",&n),n!=0)
{
for(k=0;k<n*(n-1)/2;k++)
scanf("%d%d%d",&s[k].x,&s[k].y,&s[k].cost);
qsort(s,k,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
make_set(i);
ans=0;
for(i=0;i<k;i++)
{
x=find(s[i].x);
y=find(s[i].y);
if(x!=y)
Union(x,y,s[i].cost);
}
printf("%d\n",ans);
}
return 0;
}

Answer 1

你的程序的错误在于一个小小的细节。题目中说村庄的编号是从1到N，而你在对数组f和rank赋初始值的时候是从0到N-1赋的，也未对输入的村庄编号进行减1处理，所以会出现wrong answer的情况。你只需要将for(i=0;i<n;i++)改为for(i=1;i<=n;i++)或对所有输入的村庄编号进行减1处理就能Accepted。
修改后的程序如下(这段程序采用的修改是将for(i=0;i<n;i++)改为for(i=1;i<=n;i++)):
#include<stdio.h>
#include<stdlib.h>
#define N 105
#define MAX 50005
typedef struct{
int x,y,cost;
}edge;
edge s[MAX];
int ans,f[N],rank[N];
int cmp(const void *a,const void *b)
{
return ((edge *)a)->cost-((edge *)b)->cost;
}
void make_set(int x)
{
f[x]=x;
rank[x]=0;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void Union(int x,int y,int cost)
{
ans+=cost;
if(rank[x]>rank[y])
f[y]=x;
else
{
if(rank[x]==rank[y])
rank[y]++;
f[x]=y;
}
}
int main()
{
int i,n,k,x,y;
while(scanf("%d",&n),n!=0)
{
for(k=0;k<n*(n-1)/2;k++)
scanf("%d%d%d",&s[k].x,&s[k].y,&s[k].cost);
qsort(s,k,sizeof(s[0]),cmp);
for(i=1;i<=n;i++)
make_set(i);
ans=0;
for(i=0;i<k;i++)
{
x=find(s[i].x);
y=find(s[i].y);
if(x!=y)
Union(x,y,s[i].cost);
}
printf("%d\n",ans);
}
return 0;
}

Answer 2

自己认真调试吧，区域赛时没人会给你提供任何信息！
调试程序是种能力，别人也不一定能看懂你的代码！
而且，坦白说，搞ACM的，为了节省时间，往往变量的定义很随意，很简单，这些变量不能让人看了就知道其含义，所以，估计没人愿意仔细看这段代码吧。。。