#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());
}    

• Re:怎么过不了，老是wrong 想看看牛人怎么写的 (1337) frkstyc 2005-05-03 07:59:12
• 把已有的边权强行赋成0然后直接prim就行了 (1290) palmtenor 2005-05-03 09:46:11
  • 没想到...写毛了就直接并查集了... (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
• Re:怎么过不了，老是wrong 想看看牛人怎么写的 (5) csjxl 2008-09-15 20:34:05