请帮忙看看好吗？为什么答案对了还是WA？奇怪。用的是kruskal（初始化的时候把给定好的路径进行处理，直接加入连同集合里了）或者给些奇怪的数据吧。


测试数据为
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
2
1 2
3 4

4
0 10 10 10
10 0 1 10
10 1 0 10
10 10 10 0
1
1 2

3
0 990 692
990 0 179
692 179 0
1
2 1

答案为
1
11
179

Code：如下：

#include<stdio.h>

#define MAX 10005

 

typedef struct{
int from;
int to;
int value;
int flag;
}edge;
int vset[MAX];
int array[MAX][MAX];
edge e[MAX];

void insertsort( int n )
{
int i,j;
 
for(i=2;i<=n;i++)
{if(e[i].value<e[i-1].value){
e[0]=e[i];
e[i]=e[i-1];
for(j=i-2;e[0].value<e[j].value;j--)
{
e[j+1]=e[j];
}
e[j+1]=e[0];
}
}

}

int kruskal(int n )
{
int a,b,i,j,m1,m2,sn1,sn2,k,m;
int sum=0;

k=1;

for(i=1;i<=n;i++)
 vset[i]=i;

scanf("%d",&m);
for(i=1;i<=m;i++)
{scanf("%d %d",&a,&b);
array[a][b]=-1;
array[b][a]=-1;
vset[a]=-2;vset[b]=-2;
}




for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
   {
   if(array[i][j]!=0&&array[i][j]!=-1)
     {e[k].from=i;e[k].to=j;e[k].value=array[i][j];e[k].flag=0;k++;}
else if(array[i][j]==-1)
{e[k].from=i;e[k].to=j;e[k].value=0;e[k].flag=1;k++;}
    }


insertsort(n);


k=1;j=1;

while(k<n-m)
{
m1=e[j].from;
m2=e[j].to;
sn1=vset[m1];
sn2=vset[m2];
if(sn1!=sn2)  {
k++;e[j].flag=1;
sum=e[j].value+sum;
for(i=1;i<=n;i++) if(vset[i]==sn2) vset[i]=sn1;}
j++;

}
return sum;

}


 

int main()
{ 
int i,j;
int n,sum  ;
 
 while(scanf("%d",&n)!=EOF){

for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  {
  scanf("%d",&array[i][j]);
  }

sum=kruskal(n);

printf("%d\n",sum);}
 
return 0;}

• Re:请帮忙看看好吗？为什么答案对了还是WA？奇怪。用的是kruskal（初始化的时候把给定好的路径进行处理，直接加入连同集合里了）或者给些奇怪的数据吧。 (1892) 0o0o0o0o0o0 2007-11-28 10:48:00
• Re:请帮忙看看好吗？为什么答案对了还是WA？奇怪。用的是kruskal（初始化的时候把给定好的路径进行处理，直接加入连同集合里了）或者给些奇怪的数据吧。 (1892) Brdy0013 2009-03-30 21:21:19
  • 数据是不对的 。。 a<b 你给的a>b了。。 (0) Brdy0013 2009-03-30 21:21:52