2418. Wormhole Sort

2418. Wormhole Sort

(File IO): input:wormsort.in output:wormsort.out
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
Goto ProblemSet

---

题目描述

Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。
今天早上，如同往常一样，Farmer John 的 N 头编号为 1…N 的奶牛（1≤N≤10^5），分散在牛棚中 N 个编号为 1…N 的不同位置，奶牛 i 位于位置 pi。但是今天早上还出现了 M 个编号为 1…M 的虫洞（1≤M≤10^5），其中虫洞 i 双向连接了位置 ai 和 bi，宽度为 wi（1≤ai,bi≤N,ai≠bi,1≤wi≤10^9）。
在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换，直到对于 1≤i≤N，奶牛 i 位于位置 i。
奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。

输入

输入的第一行包含两个整数 N 和 M。
第二行包含 N 个整数 p1,p2,…,pN。保证 p 是 1…N 的一个排列。
对于 1 到 M 之间的每一个 i，第 i+2 行包含整数 ai、bi 和 wi。

输出

输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序，输出 −1。

样例输入

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

样例输出

9

数据范围限制

测试点 1-5 满足 N,M≤1000。
测试点 6-10 没有额外限制。

提示
​以下是一个仅用宽度至少为 9 的虫洞给奶牛排序的可能方案：

奶牛 1 和奶牛 2 使用第三个虫洞交换位置。
奶牛 1 和奶牛 3 使用第一个虫洞交换位置。
奶牛 2 和奶牛 3 使用第三个虫洞交换位置。

主要数据结构：并差集
题目大意：让第i头牛回到第p[i]个牛场。

 用并查集就是判断一下第i头牛和第p[i]个牛场是否在同一个
 集合（集合内所有的牛都可进行交换），如果他们的祖先相同，
 那么便能归位。

方法一

对于输入数据，先按照虫洞宽度做一遍降序排列(一旦满足条件，就一定是最优解)，最后只需模拟一下交换的过程即可。
但是不能去每次都判断牛是否归位，因为会超时。
仔细推敲，我们便能知道一条性质：

如果当前点已经归位，在以后的交换中是不影响的。
明白这个以后，我们就只有统计一下归位的牛数就行。
时间复杂度：O（m+n）;

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e5+10;
struct node
{
	int u,v,w;
} cow[N];
int n,m,p[N],f[N];
bool ff;
void input()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&p[i]);   
		if(p[i]!=i) ff=1;  
		f[i]=i;	
	}
	for(int i=1;i<=m;i++) scanf("%d%d%d",&cow[i].u,&cow[i].v,&cow[i].w);
}
bool cmp(node x,node y) {return x.w>y.w;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main()
{
	//fre(wormsort);
	input();
	if(!ff) //特判一开始全都在原位 
	{
		printf("-1");  
		return 0;	
	}
	sort(cow+1,cow+1+m,cmp);
	int j=1;
	for(int i=1;i<=m;i++)
	{
		int a=find(cow[i].u),b=find(cow[i].v);
		if(a!=b) f[a]=f[b]; 
		while(find(p[j])==find(j)) j++;  
		//当一个点已经满足要求时，那么在加边还是满足要求
		//j巧用数组下标，因为没有第0头牛
		if(j>n) 
		{
			printf("%d\n",cow[i].w);
			return 0;
		}
	}
	return 0;
}

方法二

其实思路与上述一样，只是我们不需要一个个去枚举虫洞当最小距离。
数据满足有序性，所以可考虑用二分（最小距离）。
但是要注意一点：如果是用降序排序，那么你的l就应等于最后一个值，r等于第一个值，因为l<=r。
时间复杂度：O（nlogn);

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e5+10;
struct node
{
	int u,v,w;
} cow[N];
int n,m,p[N],f[N],l,r;
bool ff;
void input()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&p[i]);   
		if(p[i]!=i) ff=1;  
	}
	for(int i=1;i<=m;i++) scanf("%d%d%d",&cow[i].u,&cow[i].v,&cow[i].w);
}
bool cmp(node x,node y) {return x.w>y.w;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
bool check(int minl)
{
	int j=1;
	for(int i=1;i<=n;i++) f[i]=i;	
	for(int i=1;i<=m&&cow[i].w>=minl;i++)
	{
		int a=find(cow[i].u),b=find(cow[i].v);
		f[a]=b;
	}
	for(int i=1;i<=n;i++) if(find(i)!=find(p[i])) return 0;
	return 1;
}
int main()
{
	//fre(wormsort);
	input();
	if(!ff) //特判一开始全都在原位 
	{
		printf("-1");  
		return 0;	
	}
	sort(cow+1,cow+1+m,cmp);
	int l=cow[m].w,r=cow[1].w,mid,ans;
	while(l<=r)
	{
		mid=(l + r) >> 1;
		if(check(mid)) l = mid+1,ans=mid;
		else r = mid-1;
	}
	printf("%d",ans);
	return 0;
}