最小生成树ｋｒｕｓｋａｌ

编写一个程序，对于给定的加权图G=（v，E），输出其最小生成树的各边权值总和。

输入：

第一行v e G的顶点数和边数。

后面的，si ti wi si ti 表示连接的两个顶点的编号。wi 表示第i条边的权值

输出：

最小生成树的各边权值总和。占一行。

限制：

1<=|V|<=10000 0<=|E|<=100000 0<=wi<=10000 图G连通不存在多边重复不存在自身循环。

输入示例：

6 9

0 1 1

0 2 3

1 2 1

1 3 7

2 4 1

1 4 3

3 4 1

3 5 1

4 5 6

输出示例：

题解：

克鲁斯卡尔算法：

1：将图G（V，E）的边ei 按权值升序（降序）排列。

2：设最小生成树的边的集合为K，并将其初始化为空。

3：在保证K并上{ei}不出现环的前提下，按i=1，2，3，……，|E|的顺序将ei添加至K，直到|K|=|V|-1.

算法复杂度：O（|E|log|E|）。

代码： 最小生成树ｋｒｕｓｋａｌ

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=10000;
const int INF=(1<<29);
class DisjointSet
{
public:
    vector<int>rank,p;
    DisjointSet(){}
    DisjointSet(int size)
    {
        rank.resize(size,0);
        p.resize(size,0);
        for(int i=0;i<size;i++)
            makeSet(i);
    }
    void makeSet(int x)
    {
        p[x]=x;
        rank[x]=0;
    }
    bool same(int x,int y)
    {
        return findSet(x)==findSet(y);
    }
    void unite(int x,int y)
    {
        link(findSet(x),findSet(y));
    }
    void link(int x,int y)
    {
        if(rank[x]>rank[y])
        {
            p[y]=x;
        }
        else
        {
            p[x]=y;
            if(rank[x]==rank[y])
            {
                rank[y]++;
            }
        }
    }
    int findSet(int x)
    {
        if(x!=p[x])
        {
            p[x]=findSet(p[x]);
        }
        return p[x];
    }
};
class Edge
{
public:
    int source,target,cost;
    Edge(int source=0,int target=0,int cost=0):source(source),target(target),cost(cost){}
    bool operator <(const Edge &e)const{return cost<e.cost;}
};
int kruskal (int N,vector<Edge>edges)
{
    int totalCost=0;
    sort(edges.begin(),edges.end());
    DisjointSet dset=DisjointSet(N+1);
    for(int i=0;i<N;i++)
    {
        dset.makeSet(i);
    }
    int source,target;
    for(int i=0;i<edges.size();i++)
    {
        Edge e=edges[i];
        if(!dset.same(e.source,e.target))
        {
            totalCost+=e.cost;
            dset.unite(e.source,e.target);
        }
    }
    return totalCost;
}
int main()
{
    int N,M,cost;
    int source,target;
    cin>>N>>M;
    vector<Edge> edges;
    for(int i=0;i<M;i++)
    {
        cin>>source>>target>>cost;
        edges.push_back(Edge(source,target,cost));
    }
    cout<<kruskal(N,edges)<<endl;
    return 0;
}

今天也是元气满满的一天！ｇｏｏｄ　ｌｕｃｋ！

最小生成树ｋｒｕｓｋａｌ

相关推荐