克鲁斯卡尔算法？？ 最小生成树 经典的畅通工程题目 杭电1102

//克鲁斯卡尔算法？？  最小生成树 经典的畅通工程题目  杭电1102 并查集
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct {
    int a,b;
    int w;//距离
}Road;

int n,v[105];
bool cmp(Road a,Road b){
    return a.w < b.w;
}
int getRoot(int a){
    while(a != v[a])  a = v[a];
    return a;
}
int main(){
    Road roads[10010];//设置1010不行
    while(cin>>n){
        int a[103][103];
        int k = 0;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                cin>>a[i][j];

        int t;
        cin>>t;
        while(t--){
            int x,y;
            cin>>x>>y;
            a[x][y] = 0;//距离置为0，说明已经修了
        }

        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;++j){ //只扫描上三角部分
            roads[k].a = i;
            roads[k].b = j;
            roads[k].w = a[i][j];
            k++;
        }

        for(int i=1;i<105;i++) v[i] = i;
        sort(roads,roads+k,cmp);
        int s = 0;
        for(int i=0;i<k;i++){
            int x1 = getRoot(roads[i].a);
            int x2 = getRoot(roads[i].b);
            if(x1 != x2){
                s +=roads[i].w;
                v[x1] = x2;
            }
        }
        cout<<s<<endl;

    }

    return 0;
}