我是贪心做的，每次找最短边接起来，然后不停的floyd-warshall去掉不需要的边

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