> 请帮忙看看好吗？为什么答案对了还是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;}
> 

• 数据是不对的 。。 a<b 你给的a>b了。。 (0) Brdy0013 2009-03-30 21:21:52