> #include <stdio.h>
> #define MAXN 101
> int n,q,xx[MAXN][MAXN];
> 
> void conn(int a,int b)
> {
>     int i,j,i0,j0,temp;
>     if (a<b)
>      {temp=a;a=b;b=temp;}
>     for(i=1;i<=n;i++)
>     {
>       xx[b][i]=((xx[a][i]<xx[b][i])?xx[a][i]:xx[b][i]);
>       xx[i][b]=((xx[i][a]<xx[i][b])?xx[i][a]:xx[i][b]);
>     }
>     for(i=a;i<=n-1;i++)
>       for(j=1;j<=n;j++)
>         xx[i][j]=xx[i+1][j];
>     for(i=1;i<=n-1;i++)
>       for(j=a;j<=n-1;j++)
>         xx[i][j]=xx[i][j+1];
>     n--;
> }
> 
> void input()
> {
>     int i,j,a,b;
>     scanf("%d",&n);
>     for(i=1;i<=n;i++)
>     {
>       for(j=1;j<=n;j++)
>         scanf("%d",&xx[i][j]);
>     }
>     scanf("%d",&q);
>     for(i=1;i<=q;i++)
>     {
>         scanf("%d%d",&a,&b);
>         conn(a,b);
>     }    
> }
> 
> int solve()
> {
>     int i,j,ci,cj,y,min;
>     y=0;
>     while(n!=1)
>     {
>         min=10000;
>         for(i=1;i<=n;i++)
>           for(j=1;j<=n;j++)
>             if(xx[i][j]<min&&i!=j)
>             {
>               min=xx[i][j];
>               ci=i;cj=j;
>             }
>         y+=xx[ci][cj];
>         conn(ci,cj);
>     }
>     return y;
> }
> 
> main()
> {
>     input();
>     printf("%d\n",solve());
> }    

• 没想到...写毛了就直接并查集了... (0) ArXoR 2005-05-03 11:12:46
  • Re:没想到...写毛了就直接并查集了... (0) zhangxiong 2005-07-13 21:53:33
• 代码提交不对，你考虑它的连通定义是：直接相连或中间只有一个中转站 (32) wangshicai100 2005-07-13 22:22:21
  • 这么老的留言都翻出来了，汗...这道题我后来ac了。原来的程序子函数有问题 (0) lagrange 2005-07-13 22:38:13
  • Re:代码提交不对，你考虑它的连通定义是：直接相连或中间只有一个中转站 (27) emailed 2008-03-06 22:34:40
• Re:把已有的边权强行赋成0然后直接prim就行了 (9) goodpeter 2007-08-11 13:50:36
  • Re:把已有的边权强行赋成0然后直接prim就行了 (26) goodpeter 2007-08-11 13:55:40