USACO 2020 Jan 银组 T3 Wormhole Sort
link
题意
给定 \(n\) 的一个排列 \(p\)，有 \(m\) 个传送门可以交换 \(x_i,y_i\) 处的两个数，分数为 \(w_i\)。求使得 \(p\) 有序的最小分数的最大值。\(n,m\leq 10^5,x_i,y_i\leq n,w_i\leq 10^9\).
题解
观察到一个传送门只要使用就可以无限使用，考虑并查集，一个集合内可以互相换。还有一个性质就是当一个传送门使用了，那么分数比它大的都可以使用。可以二分分界点，当然也可以枚举。但是不用每次都挨个枚举，前面的能满足条件后面加多少传送门它还是满足条件。复杂度 \(O(n\log n)\)，瓶颈在排序。aclink。
坑
- 记得判
-1。
代码
#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)using namespace std;
const int N=1e5+5;void solve();
int n,m,a[N],fa[N];
struct wor{int x,y,z;bool operator< (wor A){return z>A.z;}
} w[N];signed main(){int Test=1;
// scanf("%d",&Test);while(Test--) solve();return 0;
}int find(int x){if(x==fa[x]) return x;fa[x]=find(fa[x]);return fa[x];
}void solve(){scanf("%d%d",&n,&m);bool ok=0;L(i,1,n,1){scanf("%d",a+i);if(i!=a[i]) ok=1;fa[i]=i;}L(i,1,m,1){scanf("%d%d%d",&w[i].x,&w[i].y,&w[i].z);}if(!ok){printf("-1\n");return;}sort(w+1,w+m+1);int j=1;L(i,1,m,1){int fx=find(w[i].x),fy=find(w[i].y);if(fx!=fy){fa[fx]=fy;}while(find(j)==find(a[j])){j++;if(j>n){printf("%d\n",w[i].z);return;}}}
}