#include<stdio.h>

int set_connected[101]={-1};
int map[101][101]={0};
int checked[101]={0};
long sum=0;

int main()
{
    int N,Q,i,j,k,a,b,min,sign,p=0;
    
    while(scanf("%d",&N)!=EOF)
    {
        sum=0; p=0;
        for (i=0;i<101;i++) { set_connected[i]=-1; checked[i]=0; }
        for (i=0;i<N;i++)
        for (j=0;j<N;j++)
            scanf("%d",&map[i][j]);
        scanf("%d",&Q);
        if (Q==0) 
        {
             set_connected[p++]=0;
             checked[0]=1;
        } else
        for (i=0;i<Q;i++)
        {
             scanf("%d%d",&a,&b);
             if (checked[a-1]==0) 
             {
                  set_connected[p++]=a-1;
                  checked[a-1]=1;
             }
             if (checked[b-1]==0) 
             {
                  set_connected[p++]=b-1;
                  checked[b-1]=1;
             }
        }
        for (i=0;i<N&&p<N;i++)
        {
             min=10000; sign=-1;
             for (k=0;k<N;k++)
                  if (!checked[k])
                  {
                       if (sign=-1) sign=k;
                       for (j=0;j<p;j++)
                       {
                           if (map[k][set_connected[j]]!=0&&min>map[k][set_connected[j]])
                           {   sign=k;
                           min=map[sign][set_connected[j]];    }
                       }
                  }
             sum+=min;
             set_connected[p++]=sign;
             checked[sign]=1;
        }
        printf("%d\n",sum);
    }
}

• Re:那位大牛来帮忙看看，WA，不明白哪错了...最小生成树编的，拜托拉！ (52) nofree 2007-11-22 19:33:20
  • THX (0) ycdoit 2011-11-21 21:05:51