生成树算法
#include "stdio.h"

int table[105][105];
int e[5005][3];
int qu[5005];
int node[105];

int judge(int a,int b)
{
    if(e[qu[a]][2]>e[qu[b]][2])return 1;
    if(e[qu[a]][2]<e[qu[b]][2])return -1;
    return 0;
}

void swap(int a,int b)
{
    int t;
    t=qu[a];
    qu[a]=qu[b];
    qu[b]=t;
}

int partion(int low,int high,int p)
{
    while(low<=high)
    {
        if(low<p)
        {
            if(judge(low,p)>0){swap(low,p);p=low;}
            low++;
        }
        else
        {
            if(high>p)
            {
                if(judge(high,p)<0){swap(high,p);p=high;}
            }
            high--;
        }
    }
    return p;
}

void qsort(int left,int right)
{
    int middle;
    if(left<right)
    {
        middle=(left+right)/2;
        middle=partion(left,right,middle);
        qsort(left,middle-1);
        qsort(middle+1,right);
    }
}

void make(int p)
{
    int i;
    for(i=0;i<p;i++)node[i]=-1;
}

int find(int a)
{
    int i;
    if(node[a]<0)return a;
    i=find(node[a]);
    node[a]=i;
    return i;
}

void un(int a,int b)
{
    int ra=find(a);
    int rb=find(b);

    if(node[ra]<node[rb]){node[ra]+=node[rb];node[rb]=ra;}
    else {node[rb]+=node[ra];node[ra]=rb;}
}

int main()
{
    int n,q,l,r;
    int i,j,en;
    int sum;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&table[i][j]);
            }
        }

        scanf("%d",&q);
        for(i=0;i<q;i++)
        {
            scanf("%d%d",&l,&r);
            table[l-1][r-1]=table[r-1][l-1]=0;
        }

        en=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {    
                if(j<i){e[en][0]=i;e[en][1]=j;e[en++][2]=table[i][j];}
            }
        }

        for(i=0;i<en;i++)qu[i]=i;
        qsort(0,en-1);

        sum=0;
        make(n);
        for(i=0;i<en;i++)
        {
            if(find(e[qu[i]][0])!=find(e[qu[i]][1]))
            {
                sum+=e[qu[i]][2];
                un(e[qu[i]][0],e[qu[i]][1]);
            }
        }

        printf("%d\n",sum);
    }
    return 0;
}