POJ－3207－Ikki's Story IV Panda's Trick

POJ 2-sat六题之一

解题报告：http://blog.sina.com.cn/s/blog_64675f540100k13v.html

题意：平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，使这些边都不相交。

这题主要是了解把边看成是2-sat的变量。边的里边和外边对应变量的true和false;

解题报告：

题意可能刚开始不是很好理解，比如1 5连边，2，6连边，由于点是顺序排列的，一画图就可以发现，这两条边必须一个从圆外面连，一个从内部连，否则就会相交。如果再加入3 7这条边，那么就必须相交了。

这样，就可以转化成标准的2-sta问题：

1：每个边看成2个点：分别表示在内部连接和在外部连接，只能选择一个。计作点i和点i'

2：如果两条边i和j必须一个画在内部，一个画在外部（一个简单判断就可以）

那么连边：

i->j’, 表示i画内部的话，j只能画外部，即j’

j->i’，同理

i’->j，同理

j’->i，同理

// File Name: 3207.cpp
// Author: zlbing
// Created Time: 2013/1/22 18:45:07

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include <stack>
using namespace std;
#define MAXN 1020
struct TwoSAT{
    int n;
    vector<int>G[MAXN*2];
    bool mark[MAXN*2];
    stack<int>S;
    bool dfs(int x)
    {
        if(mark[x^1])return false;
        if(mark[x])return true;
        mark[x]=true;
        S.push(x);
        for(int i=0;i<G[x].size();i++)
        {
            int v=G[x][i];
            if(!dfs(v))return false;
        }
        return true;
    }
    void init(int _n)
    {
        n=_n;
        for(int i=0;i<2*n;i++)
            G[i].clear();
        memset(mark,0,sizeof(mark));
    }
/*    void add_clause(int x,int xval,int y,int yval)
    {
        x=x*2+xval;
        y=y*2+yval;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
*/
    void add_clause(int x,int y)
    {
        x=2*x;
        y=2*y;
        G[x].push_back(y+1);
        G[x+1].push_back(y);
        G[y].push_back(x+1);
        G[y+1].push_back(x);
    }
    bool solve()
    {
        for(int i=0;i<2*n;i=i+2)
        {
            if(!mark[i]&&!mark[i+1]){
                  while(!S.empty())
                  {
                      S.pop();
                  }
                if(!dfs(i))
                {
                    while(!S.empty())
                    {
                        mark[S.top()]=false;
                        S.pop();
                    }
                    if(!dfs(i+1))return false;
                }
            }
        }
        
//        for(int i=0;i<2*n;i++)
//            if(mark[i])printf("%d ",T[i/2][i%2]);
//        printf("\n");
        return true;
    }
};

int T[MAXN][2];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&T[i][0],&T[i][1]);
            if(T[i][0]>T[i][1])swap(T[i][0],T[i][1]);
        }
        TwoSAT solver;
        solver.init(m);
        for(int i=0;i<2*m;i+=2)
            for(int j=i+2;j<2*m;j+=2)
            {
                if(T[i/2][0]>T[j/2][0]&&T[i/2][0]<T[j/2][1]&&T[i/2][1]>T[j/2][1]||T[j/2][0]>T[i/2][0]&&T[j/2][0]<T[i/2][1]&&T[j/2][1]>T[i/2][1])
                    solver.add_clause(i,j);
            }
        if(solver.solve())
            printf("panda is telling the truth...\n");
        else 
            printf("the evil panda is lying again\n");
        
    }
    return 0;
}