题解【洛谷P6004】[USACO20JAN]Wormhole Sort S

题面

看到 最小值最大，一眼二分。

首先对虫洞按照 (w) 从小到大排序。

二分答案 (mid)，使得最小值最大为 (w_{mid})。

check 的话可以考虑并查集维护连通性，如果 (p_i) 与 (i) 不在一个连通块内就说明 (mid) 不符合要求。

还算是比较简单的一道题目吧。

#include <bits/stdc++.h>

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int INF = 0x3f3f3f3f, N = 100003, M = N << 1;

int n, m;
int p[N];
int fa[N];
struct Node
{
	int a, b, w;
} x[N];

inline bool cmp(Node x, Node y)
{
	return x.w < y.w;
}

int getf(int u)
{
	if (fa[u] == u) return u;
	return fa[u] = getf(fa[u]);
}

inline bool check(int mid)
{
	for (int i = 1; i <= n; i+=1) fa[i] = i;
	for (int i = mid; i <= m; i+=1)
	{
		int u = getf(x[i].a), v = getf(x[i].b);
		fa[u] = v;
	}
	for (int i = 1; i <= n; i+=1)
		if (getf(i) != getf(p[i]))
			return false;
	return true;
}

int main()
{
    n = gi(), m = gi();
    bool fl = true;
    for (int i = 1; i <= n; i+=1) 
    {
    	p[i] = gi();
    	if (p[i] != i) fl = false;
    }
    for (int i = 1; i <= m; i+=1)
    	x[i].a = gi(), x[i].b = gi(), x[i].w = gi();
    if (fl) {puts("-1"); return 0;}
    sort(x + 1, x + 1 + m, cmp);
    int l = 1, r = m, ans = 0;
    while (l <= r)
    {
    	int mid = (l + r) >> 1;
    	if (check(mid)) ans = x[mid].w, l = mid + 1;
    	else r = mid - 1;
    }
    printf("%d
", ans);
    return 0;
}