首页 > 代码库 > 【BZOJ1997】[Hnoi2010]Planar 2-SAT

【BZOJ1997】[Hnoi2010]Planar 2-SAT

2024-10-08 02:55:01   216人阅读

【BZOJ1997】[Hnoi2010]Planar

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

2
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
1 4 2 5 3 6
5 5
1 2
2 3
3 4
4 5
5 1
1 2 3 4 5

Sample Output

NO
YES

题解：跟HDU的某熊猫题一模一样？（然而我并没有写那题的题解~）

本题可以理解为圆上有一些点之间要连线，这些线要么在圆里要么在圆外，问能否让所有的线都不相交。

直接枚举出每对可能相交的线，然后一个在圆里另一个就必须在圆外，所以从A向B‘连边，从B向A‘连边就行了。

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,m,T,cnt,tot,sum,top;int to[1000010],next[1000010],head[2010],dep[2010],low[2010],ins[2010],sta[2010],bel[2010];int p[2010],pa[20010],pb[20010];int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}void tarjan(int x){	dep[x]=low[x]=++tot,ins[x]=1,sta[++top]=x;	for(int i=head[x];i!=-1;i=next[i])	{		if(!dep[to[i]])	tarjan(to[i]),low[x]=min(low[x],low[to[i]]);		else	if(ins[to[i]])	low[x]=min(low[x],dep[to[i]]);	}	if(dep[x]==low[x])	{		int t;		sum++;		do		{			t=sta[top--],ins[t]=0,bel[t]=sum;		}while(t!=x);	}}void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}void work(){	memset(head,-1,sizeof(head));	memset(dep,0,sizeof(dep));	n=rd(),m=rd(),cnt=tot=sum=0;	int i,j,a,b;	for(i=0;i<m;i++)	pa[i]=rd(),pb[i]=rd();	for(i=1;i<=n;i++)	p[rd()]=i;	if(m>3*n-6)	{		printf("NO\n");		return ;	}	for(i=0;i<m;i++)	{		pa[i]=p[pa[i]],pb[i]=p[pb[i]];		if(pa[i]>pb[i])	swap(pa[i],pb[i]);		if(pa[i]+1==pb[i])	continue;		for(j=0;j<i;j++)		{			if(pa[j]+1==pb[j])	continue;			if((pa[j]>pa[i]&&pa[j]<pb[i]&&pb[j]>pb[i])||(pa[j]<pa[i]&&pb[j]>pa[i]&&pb[j]<pb[i]))				add(i<<1|1,j<<1),add(j<<1|1,i<<1),add(i<<1,j<<1|1),add(j<<1,i<<1|1);		}	}	for(i=0;i<2*m;i++)	if(!dep[i])	tarjan(i);	for(i=0;i<m;i++)	if(bel[i<<1]==bel[i<<1|1])	{		printf("NO\n");		return ;	}	printf("YES\n");	return ;}int main(){	T=rd();	while(T--)	work();	return 0;}

【BZOJ1997】[Hnoi2010]Planar 2-SAT


联系
我们