1997: [Hnoi2010]Planar

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 2224  Solved: 824

[][][]

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

HINT

 

Source

　　为了做这道题我生生看了大半个小时的各种不靠谱的平面图课件，然后题解告诉我平面图的性质就用到了m>n*3-6不是平面图而且他只是用来剪枝的？Exucse me？

　　然后又发现这道题是2-SAT，一个坑了几乎所有NOI2017选手的知识点，然后又斯巴达了一个多小时的2-SAT，回过头来却发现我连如何判断两条边是否会相交都不懂。QAQ……

　　然后赶紧向大佬求助，既然这道题把环都给我们了，那么只要两个线段的四个端点是交错排列的那么他们如果把它们同时放在圆内或圆外他们就会相交。这也就是为什么要用2-SAT了。我们可以把它看作2-SAT的一个经典问题：n各组，每组两个人，其中有些人和别的组里的人不能一起选，每个组里必须选一个人，问能否找到合法方案。在这道题里，每一个不在圆上的线段就是我们的组，两个人就是在圆内还是圆外，跑一遍2-SAT即可。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 #include
              
                9 #define N 300 10 using namespace std; 11 struct ro{ 12 int to; 13 int next; 14 }road[600*600*2]; 15 int t,n,m,zz,a[5000],f[20005][2],pos[N],zz1; 16 void build(int x,int y) 17 { 18 zz++; 19 road[zz].to=y; 20 road[zz].next=a[x]; 21 a[x]=zz; 22 } 23 int dfn[5000],low[5000],zz2,top,st[5000],bel[5000],zz3; 24 bool rd[5000],rd2[5000]; 25 void tar(int x) 26 { 27 zz2++; 28 dfn[x]=low[x]=zz2; 29 top++; 30 st[top]=x; 31 rd[x]=rd2[x]=1; 32 for(int i=a[x];i>0;i=road[i].next) 33 { 34 int y=road[i].to; 35 if(!rd2[y]) 36 { 37 tar(y); 38 low[x]=min(low[x],low[y]); 39 } 40 else if(rd[y]) 41 { 42 low[x]=min(dfn[y],low[x]); 43 } 44 } 45 if(dfn[x]==low[x]) 46 { 47 zz3++; 48 int v; 49 do{ 50 v=st[top]; 51 top--; 52 rd[v]=0; 53 bel[v]=zz3; 54 }while(dfn[v]!=low[v]); 55 } 56 } 57 int main(){ 58 scanf("%d",&t); 59 while(t--) 60 { 61 memset(a,0,sizeof(a)); 62 top=0; 63 memset(rd2,0,sizeof(rd2)); 64 zz3=zz2=0; 65 memset(low,0,sizeof(low)); 66 memset(dfn,0,sizeof(dfn)); 67 zz=zz1=0; 68 memset(bel,0,sizeof(bel)); 69 scanf("%d%d",&n,&m); 70 for(int i=1;i<=m;i++) 71 { 72 scanf("%d%d",&f[i][0],&f[i][1]); 73 } 74 for(int i=1;i<=n;i++) 75 { 76 int x; 77 scanf("%d",&x); 78 pos[x]=i; 79 } 80 if(n*3-6
               
                to)swap(fr,to); 90 if(to-fr==1||(to==n&&fr==1))continue; 91 zz1++; 92 f[zz1][0]=fr,f[zz1][1]=to; 93 } 94 m=zz1; 95 for(int i=1;i<=m;i++) 96 { 97 for(int j=i+1;j<=m;j++) 98 { 99 if(f[i][0]
                
                 
                  f[j][0])100 {101 build(i*2,j*2-1);102 build(j*2-1,i*2);103 build(j*2,i*2-1);104 build(i*2-1,j*2);105 }106 else if(f[j][0]