P6004 [USACO20JAN] Wormhole Sort S

[USACO20JAN] Wormhole Sort S - 洛谷

算法：并查集+二分答案

难度：普及+/提高

首先我们可以发现一个性质：
当我们知道用几个虫洞进行排序的时候，我们也会知道

（1）她们用来排序的虫洞宽度的最小值；

（2）那些位置是可以相互到达的。

在这条性质的基础上，我们想到了二分答案。

接下来，就是二分答案的条件。

只要判断在开通这些虫洞的情况下，位置i与p_i是否可以相互到达，所以使用并查集。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
int n,m,pos[N],fa[N];
struct Node
{
	int a,b,w;
}e[N];

bool cmp (Node p,Node q)
{
	return p.w>q.w;
}

int read ()
{
	int s=0,k=1;char c=getchar ();
	while (!isdigit (c)) {if (c=='-') k=-1;c=getchar ();}
	while (isdigit (c)) {s=s*10+c-'0';c=getchar ();}
	return k*s;
}

void Init ()
{
	n=read ();m=read ();
	bool flag=true;
	for (int i=1;i<=n;i++)
	{
		pos[i]=read ();
		if (pos[i]!=i) flag=false;
	}
	if (flag==true)
	{
		puts ("-1");
		exit (0);
	}
	for (int i=1;i<=m;i++)
		e[i].a=read (),e[i].b=read (),e[i].w=read ();
}

int Find (int x)
{
	if (x==fa[x]) return x;
	return fa[x]=Find (fa[x]);
}

void Merge (int x,int y)
{
	int r1=Find (x),r2=Find (y);
	if (r1!=r2) fa[r2]=r1;
}

bool check (int nn)
{
	for (int i=1;i<=n;i++)
		fa[i]=i;
	for (int i=1;i<=nn;i++)
		Merge (e[i].a,e[i].b);
	for (int i=1;i<=n;i++)
		if (Find (i)!=Find (pos[i])) return false;
	return true;
}

void Work ()
{
	sort (e+1,e+1+m,cmp);
	int L=1,R=m,ans=-1;
	while (L<=R)
	{
		int mid=(L+R)/2;
		if (check (mid))
		{
			ans=e[mid].w;
			R=mid-1;
		}
		else L=mid+1;
	}
	cout<<ans<<endl;
}

int main ()
{
	Init ();
	Work ();
	return 0;
}