https://www.luogu.org/problemnew/solution/P1111

并查集的水題，水題都錯了好多發(fā)。

首先并不是有環(huán)就退出，而是連通分支為1才退出，每次合并成功連通分支才會減1。

還有一個bug就是假如沒有到達連通分支為1，不應(yīng)該輸出maxt而是要輸出-1。所以應(yīng)該是在cnt==1的情況再更新maxt并break才對。

#include<bits/stdc++.h> using namespace std; #define ll long longint n,m; struct edge{int x,y,t;bool operator<(edge that){return t<that.t;} }e[100005];int p[1005]; int _rank[1005]; struct union_find_set{void init(){for(int i=1;i<=1000;i++){p[i]=i;_rank[i]=1;}}int _find(int x){if(p[x]!=x)return p[x]=_find(p[x]);elsereturn x;}bool union_set(int x,int y){int fx=_find(x);int fy=_find(y);if(fx==fy){return false;}else{if(_rank[fx]<=_rank[fy]){if(_rank[fx]==_rank[fy])_rank[fy]++;p[fx]=fy;}else{p[fy]=fx;}return true;}} };int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].t);}sort(e,e+m);union_find_set s;s.init();int maxt=-1;int cnt=n;for(int i=0;i<m;i++){if(s.union_set(e[i].x,e[i].y)==false){maxt=e[i].t;}else{maxt=e[i].t;cnt--;if(cnt==1)break;}}/*if(maxt==-1){maxt=e[m-1].t;for(int i=1;i<=n;i++){s._find(i);}for(int i=2;i<=n;i++){if(p[i]!=p[i-1]){maxt=-1;break;}}}*/if(cnt!=1)maxt=-1;printf("%d\n",maxt); }

?

.

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yinku/p/10306475.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 - P1111 - 修复公路 - 并查集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。