样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明
下图是样例说明。
这道题看题干很麻烦,但是想一想,要求用时最少的树结构,也就是求每层次中的最大值,再比较所有层次中的最大值,让这个总最大值最小。那么可以想到,让这种最大值最小,得到的肯定是这个图的最小生成树。那么这个问题其实就是求这个图的最小生成树的最长边。
对最小生成树,我们可以采用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);} //并查集查找,返回对两元素根节点的判等