P1111 【修复公路】 并查集，联通块

这个题要求的是什么时候所有村庄互相联通，因此要找出什么时候所有点可以连成一个联通块；这就是并查集的工作了。 题目要求“最早什么时候任意两个村庄能够通车”，那么根据贪心，这个“最早”就是从前往后数第一个满足条件的时刻。因此我们需要快速排序将各个操作按顺序来一遍。 解法1 ```cpp #include<cstdio> #include<algorithm> int s[1001]; struct node { int x,y,t; node(int x,int y,int t) { this->x=x; this->y=y; this->t=t; } node(){} friend bool operator <(node a,node b) { return a.t<b.t; } }e[100001]; int my_find(int x) { if(s[x]==x) return x; return s[x]=my_find(s[x]); } void my_union(int x,int y) { s[my_find(y)]=my_find(x); } int n; bool check() { for(int i=2;i<=n;i++) if(my_find(i)!=my_find(i-1)) return false; return true; } int main() { int m,a,b,c; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) s[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); e[i]=*new node(a,b,c); } std::sort(e+1,e+1+m); for(int i=1;i<=m;i++) { my_union(e[i].x,e[i].y); if(check()) { printf("%d\n",e[i].t); return 0; } } printf("-1\n"); return 0; } ```  只T了一个点，emmm数据有点水。无论如何，暴力是过不了的。时间复杂度$O(N^2)$ ------------ 那么是不是每个时刻都需要检查呢？如果每个点每个时刻都检查，这样的时间复杂度加上常数应该是够呛的。因此我们可以选择二分答案来降低时间复杂度。 解法2 ```cpp #include<cstdio> #include<algorithm> int s[1001]; struct node { int x,y,t; node(int x,int y,int t) { this->x=x; this->y=y; this->t=t; } node(){} friend bool operator <(node a,node b) { return a.t<b.t; } }e[100001]; int my_find(int x) { if(s[x]==x) return x; return s[x]=my_find(s[x]); } void my_union(int x,int y) { s[my_find(y)]=my_find(x); } int n,m; bool check(int t) { for(int i=1;i<=n;i++) s[i]=i; int i=1; while(e[i].t<=t&&i<=m) { my_union(e[i].x,e[i].y); i++; } for(int i=2;i<=n;i++) if(my_find(i)!=my_find(i-1)) return false; return true; } int main() { int a,b,c; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); e[i]=*new node(a,b,c); } std::sort(e+1,e+1+m); int l=1,r=100001,mid=(l+r)/2; while(l<r) { mid=(l+r)/2; if(!check(mid)) l=mid+1; else r=mid; } if(l>100000) printf("-1\n"); else printf("%d\n",l); return 0; } ``` 用二分答案优化可以AC本题，时间复杂度为$O(Nlog_2n)$ ------------ **还有没有更方便更简单的解法呢？** 就是开头提到的联通块问题。并查集每并两个的点，可以判断是否属于同一个集合，如果属于同一个集合，则没有影响，如果不属于同一个集合，联通块数目$-1$，一开始有$n$个点，那么就是$n$个联通块了，这样，这道题的$O(N)$做法就出来了。 ```cpp #include<cstdio> #include<algorithm> int s[1001]; int my_find(int x) { if(s[x]==x) return x; return s[x]=my_find(s[x]); } void my_union(int x,int y) { s[my_find(y)]=my_find(x); } struct node { int s,e,t; node(int s,int e,int t) { this->s=s; this->e=e; this->t=t; } node(){} friend bool operator <(node a,node b) { return a.t<b.t; } }r[100002]; int main() { int n,m,a,b,c; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) s[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); r[i]=*(new node(a,b,c)); } std::sort(r+1,r+1+m); int cnt=n,i; for(i=1;i<=m;i++) { if(my_find(r[i].s)!=my_find(r[i].e)) { my_union(r[i].s,r[i].e); cnt--; if(cnt==1) { printf("%d\n",r[i].t); return 0; } } } printf("-1\n"); return 0; } ```