acm专题---最小生成树

#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<stack>
#include<string.h>

const int maxnum=101;
int mymap[maxnum][maxnum];
int n;
int fa[maxnum];
struct edge{
    int point1;
    int point2;
    int weight;
    edge(int _point1,int _point2,int _weight)
    {
        point1=_point1;
        point2=_point2;
        weight=_weight;
    }
};
int cmp(edge a,edge b)
{
    return a.weight<b.weight;
}
int findfa(int x)
{
    return fa[x]==x?x:(fa[x]=findfa(fa[x]));
}

void mergefa(int x,int y)
{
    fa[findfa(x)]=findfa(fa[y]);
}

void kruscal()
{
    vector<edge> edges;
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            edges.push_back(edge(i,j,mymap[i][j]));
        }
    }
    sort(edges.begin(),edges.end(),cmp);
    
    int m=n*(n-1)/2;
    int cnt=0;
    int ans=0;
    for(int i=0;i<m;i++)
    {
        int x1=edges[i].point1;
        int x2=edges[i].point2;
        int fa1=findfa(x1);
        int fa2=findfa(x2);
        
        if(fa1!=fa2)
        {
            mergefa(x1,x2);
            cnt+=1;
            ans+=edges[i].weight;
            if(cnt>=n-1) break;
        }
    }
    
    cout<<ans<<endl;
    
}
int main()
{
    
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>mymap[i][j];
            }
        }
        for(int i=0;i<=n;i++)
            fa[i]=i;
        int m;
        cin>>m;
        for(int i=0;i<m;i++)
        {
            int x,y;
            cin>>x>>y;
            mymap[x-1][y-1]=mymap[y-1][x-1]=0;
        
        }
        kruscal();
        
    }
    return 0;
}

/*
 
 Sample Input
 3
 0 990 692
 990 0 179
 692 179 0
 1
 1 2
 
 
 Sample Output
 179

 
 */