bzoj 1997: [Hnoi2010]Planar （2-SAT）

Description

Input

Output

Sample Input

Sample Output

HINT

Source

Day1

题解：2-SAT

哎，调了好久啊，真是越来越水了，数组都能开小。。。。

这道题给出了一个哈密尔顿环，环上的边一定是不冲突的。我们在环的基础上去判断其他的边。

对于其他边来说，可以从环内连也可以从环外连，如果两条边在同侧会产生交点，必然不行。

x'->y x->y' x表示从环内连，x'表示从环外连。

如果考虑所有的边是m^2的时间和空间，必然不行啊。

其实可以把环展成链，然后就能发现对于每个点来说，只需要保留从这个点出发能到达的最靠左和最靠右的点即可。

那么就可以用2-SAT判断啦。

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#define N 300003using namespace std;int n,m,T,tot,cnt,sz,top,tt;int dfsn[N],low[N],st[N],ins[N],belong[N];int point[N],v[N],nxt[N],x[N],y[N],a[N],mp[N],mark[N];struct data{	int x,y;}e[N];void init(){	top=0; cnt=sz=tot=0; tt=0;	memset(point,0,sizeof(point));	memset(ins,0,sizeof(ins));	memset(dfsn,0,sizeof(dfsn));	memset(mark,0,sizeof(mark));}int cmp(data a,data b){	return a.x<b.x||a.x==b.x&&a.y<b.y;}void build (int x1,int  y1){	if (mp[x1]>mp[y1]) swap(x1,y1);	x[++tt]=x1; y[tt]=y1;//	cout<<x1<<" "<<y1<<endl;}void add(int x,int y){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;	tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;//	cout<<x<<" "<<y<<endl;}void tarjan(int x){	st[++top]=x; ins[x]=1; low[x]=dfsn[x]=++sz;	for (int i=point[x];i;i=nxt[i]) {		int j=v[i];		if (!dfsn[j]) tarjan(j),low[x]=min(low[x],low[j]);		else if (ins[j]) low[x]=min(low[x],dfsn[j]);	}	if(low[x]==dfsn[x]) {		int j; cnt++;		do{			j=st[top--];			belong[j]=cnt;			ins[j]=0;		}while (j!=x);	}}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d",&T);	while (T--) {		init();		scanf("%d%d",&n,&m);		for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);		for (int i=1;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]=i;		int t=0;		for (int i=1;i<=m;i++) {		 if (mp[x[i]]>mp[y[i]]) swap(x[i],y[i]);		 if (mp[x[i]]+1==mp[y[i]]||mp[x[i]]==1&&mp[y[i]]==n) continue;		 e[++t].x=x[i]; e[t].y=y[i]; 		 e[++t].x=y[i]; e[t].y=x[i]; 	    }	    sort(e+1,e+t+1,cmp);		for (int i=1;i<=t;i++)		 if (e[i].x!=e[i-1].x||i==t) {		 	build(e[i].x,e[i].y); 			if (i!=1&&e[i-1].x==e[i-2].x) build(e[i-1].x,e[i-1].y);		 }		for (int i=1;i<=tt;i++) 		 for (int j=1;j<=tt;j++) {		 	if (i==j) continue;		 	if (mp[x[i]]<mp[x[j]]&&mp[x[j]]<mp[y[i]]&&mp[y[j]]>mp[y[i]]) add(i+tt,j),add(i,j+tt);		 }		for (int i=1;i<=2*tt;i++) 		 if (!dfsn[i]) tarjan(i);		bool pd=true;		for (int i=1;i<=tt;i++)		 if (belong[i]==belong[i+tt]) {		 	pd=false;		 	break;		 }		if(pd) PRintf("YES/n");		else printf("NO/n");	}}