读书人

C语言的wrong answer

发布时间: 2012-04-25 19:32:32 作者: rapoo

求助C语言的wrong answer!
/*
这是题目:


Description




John是一个农场主,他有几个牧场,为了好好照顾他的牛,他必须在几个牧场之间来回,可糟糕的天气往往使得道路非常泥泞,为此John准备在牧场之间铺一些石子路,这样在下雨天也能快速地从一个牧场到另外一个牧场。但John的资金有限,为了自己能从任一个牧场都通过石子路到达另外一个牧场,他需要好好设计一下线路。请帮助John设计好线路,使得John能从任一个牧场都通过石子路到达另外一个牧场,且线路的费用最低。


输入:

第一行是一个整数K,表示有多少个测试用例,以后每个测试用例占n+1行。每个测试用例的第一行为一个整数n(3<=n<=20),表示有多少个牧场,从第二行开始为一个n*n的矩阵,矩阵元素aij表示从i个牧场到j个牧场的铺路费用。

输出:

每行输出一个测试用例的最小铺路费用。

供用的样例:
5
6
0 6 1 5 0 0
6 0 5 0 3 0
1 5 0 5 6 4
5 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
4
0 1 2 3
1 0 3 4
2 3 0 1
3 4 1 0
10
1 2 2 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9
10 10 10 10 10 10 10 10 10 10
3
0 1 0
0 0 1
0 0 0
4
0 0 1 2
0 0 2 3
0 9 2 1
0 0 3 1

*/

#include<stdio.h>
int like_sort(int a[192],int n,int m)
{
int i,j,t,k,sum=0;
for(i=0;i<n-1;i++)
{
for(t=i,j=i+1;j<n;j++)
if(a[t]>a[j]) t=j;
if(t!=i) {k=a[i];a[i]=a[t];a[t]=k;}
}
for(j=1,i=0;i<n;i++)
if((a[i]!=0)&&(j<=m))
{j++;sum=sum+a[i];}
return sum;
}
int a[192];

int main()
{
int i,j,k,n,e,w;
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
for(e=0,i=0;i<n;i++)
for(j=0;j<n*2;j+=2)
{
if(j>=2*(i+1)) scanf("%d",&a[e++]);
else scanf("%d",&w);
getchar();
}
printf("%d\n", like_sort(a,n*(n-1)/2,n-1));
}
return 0;
}

submit 后,为什么会是wrong answer????

[解决办法]
图算法---最小生成树 普利姆或克鲁斯卡尔算法
[解决办法]
对于这个示例有2个问题,
1、2个牧场间的距离是0,代表什么意思
2、楼主前几个示例数据还是对称的,但是后几个就随便写了,那怎么测试是否正确呢

读书人网 >C语言

热点推荐