CSP CCF 2018124 数据中心 并查集 kruskal算法求最小生成树 C++类

时间:2020-12-14 21:31:03

CSP CCF 2018124 数据中心 并查集 kruskal算法求最小生成树 C++类
CSP CCF 2018124 数据中心 并查集 kruskal算法求最小生成树 C++类

样例输入

4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

样例输出

4

样例说明

下图是样例说明。

CSP CCF 2018124 数据中心 并查集 kruskal算法求最小生成树 C++类

这道题看题干很麻烦,但是想一想,要求用时最少的树结构,也就是求每层次中的最大值,再比较所有层次中的最大值,让这个总最大值最小。那么可以想到,让这种最大值最小,得到的肯定是这个图的最小生成树。那么这个问题其实就是求这个图的最小生成树的最长边。

对最小生成树,我们可以采用prim算法和kruskal算法。

prim算法类似dijkstra算法,选择邻接矩阵实现,需要我们用n*n维矩阵,对于题中条件,需要用25亿个整型字符空间,显然越界了。我用prim写的程序,交上去只得了50分。为了得满分,还是需要用kruskal算法。

kruskal算法比较容易理解,就是对所有边升序排列,从最小边开始,逐次向解中加入边,每次加入前先判断,此条边加入后是否已成环,如果是,则跳过此边换下一个,如果否,就在答案生成树中加入此边。这里碰到一个问题,如何判断是否成环?

这里引入并查集数据结构,它能够在几乎线性的时间复杂度内判断元素是否属于同一个集合。则应用到该题中,就是对于新边的两端点,如果我们通过并查集查询到它们已在同一个集合内,则加入该边构成环,则不加入;如果没在同一个集合内,则加入答案生成树,并且将两端点加入同一个集合内。

并查集的实现是静态树结构,也就是数组模拟的树。每一个节点的编号同时作为集合序号,该节点作为属于这一集合的所有元素的父节点。

并查集的建立一般只包括三个函数:init()、Find()、unite()、same().

init:初始化并查集
Find:寻找目标节点的父节点,也就是代表所在的集合
unite:将两个节点合所在集合并到,合并规则依照所在集合树的高度
same:判断两个节点是否在同一个集合内

下面在答案中进一步说明并查集和kruskal算法。

补充一点,为了便于处理,我在程序中构造了一个edge类,表示边。其实class和struct差不多。

  • class中默认是private,类外调用(一般写算法竞赛代码常用类外调用)需要设置public
  • 记住其中构造函数的写法,和运算符重载的写法。
#include <bits/stdc++.h>
#define N 50005
#define M 100005
using namespace std;
int n,m,root,ans=-1;
class edge {
    public:
        int u,v,cost;
        edge() : u(0),v(0),cost(0) {}
        edge(int a,int b,int c) : u(a),v(b),cost(c){}
    bool operator < (edge const ed) const {
        return cost<ed.cost;
    }
};
edge es();
vector<edge> ve;

int par[N],h[N];    //创建并查集父节点集合par,和并查集树高集合h。h用于并查集合并。
void init(int n);   //并查集初始化函数
int Find(int a);    //并查集查找函数
bool same(int a,int b);     //并查集判断是否属于同一个集合
void unite(int a,int b);    //并查集合并函数

int main()  {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c,res=0;
    cin>>n>>m>>root;
    for (int i=0;i<m;i++)   {
        cin>>a>>b>>c;
        ve.push_back(edge(a,b,c));
    }
    init(n);
    sort(ve.begin(),ve.end());
    for (int i=0;i<(int)ve.size();i++)  {
        if (!same(ve[i].u,ve[i].v)) {               //如果该边的两定点构不成环,则该边加入解中
            unite(ve[i].u,ve[i].v);
            int t=ve[i].cost;
            res+=t;
            ans=max(t,ans);
        }
    }
    cout<<ans<<endl;
    return 0;
}

void init(int n) {
    for (int i=0;i<=n;i++)   {
        par[i]=i;           //初始化,所有的节点的父节点设为自身
        h[i]=0;             //所有并查集的高度设为0,即树高。
    }
}

int Find(int a)   {
    if (a==par[a])  return a;       //如果节点号等于父节点号,这说明找到了该集合的父节点,则返回
    return par[a]=Find(par[a]);     //路径压缩,这一步是并查集算法的精华!!!它能够将向根节点查找的路径上的所有父节点全部挂靠到根节点上,从而大大缩短并查集接下来查找的执行时间。
}

void unite(int a,int b) {
    a=Find(a);
    b=Find(b);              //原先WA是因为我这里没有对a和b的赋值,直接写了个判断 if Find(a)==Find(b),找bug找了半天。此处一定注意,要用a、b的根节点来替换a、b。
    if (a==b)   return;
    if (h[a]<h[b])  par[a]=b;       //如果a集合树高小于b集合树高,则a挂靠到b上
    else {                              //如果b集合树高小于a集合树高
        par[b]=a;                       //首先将b挂靠到a上
        if (h[a]==h[b]) h[a]++;     //然后判断ab树高是否相同,该操作是否会令a树变高。如等高,则挂靠会让a树高+1
    }
}

bool same(int a,int b)  {return Find(a)==Find(b);}      //并查集查找,返回对两元素根节点的判等