最小生成树（MST）模板---Kruskal算法

最小生成树：

    给定一个 无向图，如果它的某个子图中任意两个点都相互连通并且是一颗树，那么这棵树就叫生成树。

如果边上的权值和最小的话，生成树就叫做最小生成树。

综合简洁性和效率这里仅提供kruskal算法：

把所有边按照从小到大排序，然后每次拿出来一条边，如果边的两个端点没有在一个集合（连通分量）内，就将该边加入，否则，继续寻找下一个边，直至形成最小生成树：加入的边数==n-1。

注意：

由于是无向图，所以每条边添加的时候，只添加一次就够了！

下面给出模板：

#include<iostream>#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<cctype>

using namespace std;
const int maxn=110;

struct edge
{
    int u,v,cost;
    edge(int u,int v,int d):u(u),v(v),cost(d){}
    bool operator < (const edge& a)const
    {
        return cost<a.cost;
    }
};

int n;
vector<edge>es;//边

int pa[maxn];
int findset(int x){pa[x]<0?x:pa[x]=findset(pa[x])}//并查集

int Kruskal()
{
    int cnt=0;//已经连好的边
    int ans=0;//边权的总和
    memset(pa,-1,sizeof(pa));//并查集初始化
    sort(es.begin(),es.end());//对边按照权重进行排序

    for(int i=0;i<es.size();i++)
    {
        int u=es[i].u;
        int v=es[i].v;
        if(findset(u)!=findset(v))//两点不在一个连通分量中
        {
            pa[findset(u)]=findset(v);//unite
            ans+=es[i].cost;
            if(++cnt>=n-1)break;//最小生成树已经出来了
        }
        //不存在最小生成树输出-1。
        return cnt>=n-1? sum : -1;
    }

}


//主函数添加边，这里给出连接矩阵连加边的方式！
int main()
{
    while(cin>>n)
    {
        es.clear();

        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
        {
            int x;scanf("%d",&x);
            if(i<j)es.push_back(edge(i,j,x));//添加一次

        }
        cout<<kk()<<endl;
    }
}