看了他们的题解感觉很震惊, 为什么要用 kruskal, 这题要用到最小生成树吗???
38 行短短的程序就可以了, 我觉得学习不是一种套用, 套自己学的, 而且题解很大一部分都是 kruskal.
个人认为自己的程序比他们快.
- #include<bits/stdc++.h>
- using namespace std;
- struct node{
- int x,y,z;
- }q[100010];
- int fa[100010],num[100010];
- int n,m;
- bool f;
- int w_comp(const node a,const node b){
- return a.z<b.z;
- }
- int get(int x){
- if (x==fa[x]) return x;
- return fa[x]=get(fa[x]);
- }
- void add(int x,int y){
- fa[get(y)]=get(x);
- }
- int main(){
- cin>>n>>m;
- f=false;
- for (int i=1;i<=n;i++) {
- fa[i]=i;
- num[i]=1;// 初始化, 每一个集合中都有一个元素, 就是它自己
- }
- for (int i=1;i<=m;i++)
- cin>>q[i].x>>q[i].y>>q[i].z;
- sort(q+1,q+m+1,w_comp);// 排序, 结构体的排序在第一篇 blog 中已经讲到. 由于只要联通了就可以不用再找, 所以我们从时间少的开始加上边
- for (int i=1;i<=m;i++){
- if (get(q[i].x)!=get(q[i].y)){// 如果在一个集合再加就没有必要了, 因为之前肯定加了一次, 不然不会在一个集合
- num[get(q[i].x)]+=num[get(q[i].y)];
- num[get(q[i].y)]=0;// 其实这边用了 get5 次, 记录一下的话只要 3 次时间复杂度又降了些许
- }
- if (num[get(q[i].x)]==n){cout<<q[i].z;return 0;}
- add(q[i].x,q[i].y);// 并查集部分需要的可以看我之前的 blog
- }
- cout<<-1<<endl;
- }
这道题的关键之处就在于如何记录你的集合的元素. 经过思考我发现在主程序中增加是很好的一种选择.
来源: https://www.cnblogs.com/fnbk/p/9332869.html