[NOI2014] 魔法森林 (二分答案,并查集)

本思路仅供参考,数据强一点应该该会被卡。

本蒟蒻没有打 \(link\) - \(cut\) - \(tree\) .

而是用暴力水了过去。

具体思路很简单，先二分最少的 \(a_i\) , 再在 \(judge\) 的时候再二分 \(b_i\).

然后使用并查集来判断是否联通，复杂度 \(n(logn)^3\)

但是第一遍只有 \(75\) 分 , 于是我写了两遍二分套二分,即先是以 \(a_i\) 为第一个二分的，然后再以 \(b_i\) 为第一个二分的，最后两者取较小的答案。

然后... 就 \(AC\) 了。

暴力真的是个美妙的东西。

Code :

#include<bits/stdc++.h>

#define in(x) x=read()

#define N 50008

#define M 100008

using namespace std;

struct sj{int y,x,a,b;}a[M*2];

int n,m,ans_A=M*2,ans_B=M*2,fa[N];

int Ans_A=M*2,Ans_B=M*2,Fa[N];

int read()

{

	char ch=getchar(); int f=1,w=0;

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}

	return f*w;

}

int find(int x){

	if(x==fa[x])return x;

	return fa[x]=find(fa[x]);

}

void join(int x,int y){

	x=find(x); y=find(y);

	if(x!=y)fa[x]=y;

}

bool jud(int A,int B)

{

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1;i<=m;i++)

	if(a[i].a<=A&&a[i].b<=B)

	join(a[i].x,a[i].y);

	if(find(1)==find(n))return 1;

	return 0;

}

bool solve(int A)

{

	int L=0,R=N*2,ans=-1;

	while(L<=R)

	{

		int B=L+R>>1;

		if(jud(A,B))

			ans=B,R=B-1;

		else L=B+1;

	}

	if(ans==-1)return 0;

	if(ans_A+ans_B>A+ans)

	ans_A=A,ans_B=ans;

	return 1;

}

bool Jud(int A,int B)

{

	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1;i<=m;i++)

	if(a[i].b<=A&&a[i].a<=B)

	join(a[i].x,a[i].y);

	if(find(1)==find(n))return 1;

	return 0;

}

bool Solve(int A)

{

	int L=0,R=N*2,ans=-1;

	while(L<=R)

	{

		int B=L+R>>1;

		if(Jud(A,B))

			ans=B,R=B-1;

		else L=B+1;

	}

	if(ans==-1)return 0;

	if(Ans_A+Ans_B>A+ans)

	Ans_A=A,Ans_B=ans;

	return 1;

}

int main()

{

	//freopen("disanti.in","r",stdin);

	//freopen("disanti.out","w",stdout);

	in(n); in(m);

	for(int i=1;i<=m;i++)

		in(a[i].x),in(a[i].y),

		in(a[i].a),in(a[i].b);

	int l=0,r=N*2;

	while(l<=r)

	{

		int mid=l+r>>1;

		if(solve(mid))r=mid-1;

		else l=mid+1;

	}

	l=0,r=N*2;

	while(l<=r)

	{

		int mid=l+r>>1;

		if(Solve(mid))r=mid-1;

		else l=mid+1;

	}

	if(ans_A==M*2&&ans_B==M*2)puts("-1");

	else cout<<min(Ans_A+Ans_B,ans_A+ans_B)<<endl;

	return 0;

}

巴特西

[NOI2014] 魔法森林 (二分答案,并查集)

最新文章

热门文章