2-sat 问题

poj 3207 Ikki's Story IV - Panda's Trick http://poj.org/problem?id=3207

【题意】在一个环上有n个点 m组连线（连接这两个点的线可以在环内也可以在环外）判断这些线是否可以互不相交

（第一次写的 2-sat 还蛮顺利的 1a 哈~~）

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<vector>
  4 using namespace std;
  5 
  6 vector<int > g[1002];
  7 
  8 int vis[1002],u[1002],v[1002],c,w[1002],m,n;
  9 int max(int x,int y)
 10 {
 11     return x>y?x:y;
 12 }
 13 int min(int x,int y)
 14 {
 15     return x<y?x:y;
 16 }
 17 
 18 int ok(int i,int j)
 19 {
 20     int max1,max2,min1,min2;
 21     max1=max(u[i],v[i]);
 22     min1=min(u[i],v[i]);
 23     max2=max(u[j],v[j]);
 24     min2=min(u[j],v[j]);
 25     if(min1>min2&&min1<max2&&(max1>max2||max1<min2))
 26         return 1;
 27     if(max1>=min2&&max1<max2&&(min1>max2||min1<min2))
 28         return 1;
 29     if(min2>min1&&min2<max1&&(max2>max1||max2<min1))
 30         return 1;
 31     if(max2>min1&&max2<max1&&(min2>max1||min2<min1))
 32         return 1;
 33     return 0;
 34 }
 35 
 36 void add(int i,int j) //i 和j 交叉 也就是只能一个在里面一个在外面
 37 {
 38     int x=i*2;
 39     int y=j*2;
 40     g[x+1].push_back (y);
 41     g[y+1].push_back (x);
 42     g[x].push_back (y+1);
 43     g[y].push_back (x+1);
 44     //vis[x]=1; vis[y]=1;vis[x+1]=1; vis[y+1]=1; 
 45 }
 46 
 47 int dfs(int x)
 48 {    
 49     if(vis[x])
 50         return 1;
 51     if(vis[x^1])      // 因为2-sat 只能选其中一种情况 若在判断 选x行不行时发现 x^1 已选  选x绝对错了
 52             return 0;
 53     vis[x]=1;    w[c++]=x;    
 54     for(int i=0;i<g[x].size ();i++)
 55         if(!dfs(g[x][i]))
 56             return 0;        
 57     return 1;
 58 
 59 }
 60 
 61 int solve()
 62 {
 63     int j,i;
 64     for(i=0;i<m;i++)
 65         if(!vis[i*2]&&!vis[i*2+1])
 66         {
 67             c=0;
 68             if(!dfs(i*2))
 69             {
 70                 while(c--)
 71                     vis[w[c]]=0;
 72             
 73                 if(!dfs(i*2+1))
 74                      return 0;
 75             }
 76         }
 77         return 1;
 78 }
 79 
 80 int main()
 81 {    
 82     int i,j,t;
 83     while(scanf("%d%d",&n,&m)!=EOF)
 84     {
 85         for(i=0;i<=m*2;i++)
 86             g[i].clear ();
 87         for(i=0;i<m;i++)
 88             scanf("%d%d",&u[i],&v[i]);
 89         memset(vis,0,sizeof(vis));
 90         for(i=0;i<m;i++)
 91             for(j=i+1;j<m;j++)
 92                 if(ok(i,j))                
 93                     add(i,j);
 94                 if(solve())
 95                     printf("panda is telling the truth...
");
 96                 else
 97                     printf("the evil panda is lying again
");
 98     }
 99     return 0;
100 }

View Code