题目大意：给定一个带哈密顿回路的图，判断这个图是否是平面图
这竟然是我第一次写2-sat。。。
把哈密顿回路拎出来，每条边只有两种可能：在里面或者在外面
如果两条边相交，那么必须一条在里面一条在外面
然后建2-sat就好了。。。
10000条边显然不能暴力建图，但是我们发现如果边数>3*点数，那么这个图一定不是平面图
这样就把边数缩小到了400，然后就可以做了
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1210#define P1(x) ((x)*2-1)#define P2(x) ((x)<<1)using namespace std;struct edge{int x,y;}edges[M];int n,m,pos[M];bool On_Ring(int x,int y){x=pos[x];y=pos[y];if( abs(x-y)==1 || abs(x-y)==n-1 )return true;return false;}bool Cross(int x1,int y1,int x2,int y2){x1=pos[x1];y1=pos[y1];x2=pos[x2];y2=pos[y2];if(x1==x2||x1==y2||y1==x2||y1==y2)return false;if( x1>y1 )swap(x1,y1);int temp=0;if(x2>x1&&x2<y1)temp++;if(y2>x1&&y2<y1)temp++;return temp==1;}namespace Two_Sat_Graph{struct abcd{int to,next;}table[M*M];int head[M],tot;int belong[M],cnt;int dpt[M],low[M],T;int stack[M],top;void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Initialize(){memset(head,0,sizeof head);tot=0;memset(belong,0,sizeof belong);memset(dpt,0,sizeof dpt);}void Tarjan(int x){int i;dpt[x]=low[x]=++T;stack[++top]=x;for(i=head[x];i;i=table[i].next){if(belong[table[i].to])continue;if(dpt[table[i].to])low[x]=min(low[x],dpt[table[i].to]);elseTarjan(table[i].to),low[x]=min(low[x],low[table[i].to]);}if(dpt[x]==low[x]){int t;++cnt;do{t=stack[top–];belong[t]=cnt;}while(t!=x);}}}int main(){using namespace Two_Sat_Graph;int T,i,j,x;for(cin>>T;T;T–){Initialize();scanf("%d%d",&n,&m);if(m>3*n){for(i=1;i<=m;i++)scanf("%*d%*d");for(i=1;i<=n;i++)scanf("%*d");puts("NO");continue;}for(i=1;i<=m;i++)scanf("%d%d",&edges[i].x,&edges[i].y);for(i=1;i<=n;i++){scanf("%d",&x);pos[x]=i;}for(i=1;i<=m;i++)if( !On_Ring(edges[i].x,edges[i].y) )for(j=1;j<i;j++)if( !On_Ring(edges[j].x,edges[j].y) )if( Cross(edges[i].x,edges[i].y,edges[j].x,edges[j].y) ){Add( P1(i) , P2(j) );Add( P2(j) , P1(i) );Add( P1(j) , P2(i) );Add( P2(i) , P1(j) );}for(i=1;i<=2*m;i++)if(!belong[i])Tarjan(i);for(i=1;i<=m;i++)if(belong[P1(i)]==belong[P2(i)]){puts("NO");break;}if(i==m+1)puts("YES");}return 0;}
，去旅行不在于记忆，而在于当时的那份心情。
