poj 3207 Ikki's Story IV - Panda's Trick【2-set】

￡神魔★判官ぃ 2022-08-08 12:45 11阅读 0赞

题目：[poj 3207 Ikki’s Story IV - Panda’s Trick][poj 3207 Ikki_s Story IV - Panda_s Trick]

题意：给出一个有（0-n-1）组成的圆，然后连接上面的一些点，可以选择从圆内部连接或者内部连接，然后问你所有的都不想交可不可行

分析：对于每条Link，要么在圆外，要么在圆内，且不可同时满足，  
只能两者取一，判断这M条Link是否合法，也就是M条Link不冲突，  
这就是典型的2-sat问题了。 将每条Link i 看做一个点，如果Link在圆内，  
则选做i ，如果在圆外， 则选做i’。对于两条线(i,j) ，如果i，j不能同时  
在圆内，也就可以推出两者不能同时在圆外，建边跑2-set就ok了

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <cmath>
    #include <stack>
    #include <algorithm>
    using namespace std;
    const int N = 1200;
    
    struct TwoSet
    {
        vector<int> G[2*N];
        int s[2*N],c;
        bool vis[2*N];
        void init(int n)
        {
            for(int i=0;i<=2*n;i++)
                G[i].clear();
            memset(vis,false,sizeof(vis));
        }
        void add_Node(int x,int y)
        {
            G[x].push_back(y^1);
            G[y].push_back(x^1);
        }
        bool dfs(int x)
        {
            if(vis[x^1])
                return false;
            if(vis[x])
                return true;
            vis[x] = true;
            s[c++] = x;
            for(int i=0;i<G[x].size();i++)
            {
                if(!dfs(G[x][i]))
                    return false;
            }
            return true;
        }
        bool yougth(int n)
        {
            for(int i = 0;i< 2*n;i+=2)
            {
                if(!vis[i] && !vis[i+1])
                {
                    c = 0;
                    if(!dfs(i))
                    {
                        while(c>0)
                            vis[ s[--c] ] = false;
                        if(!dfs(i+1))
                            return false;
                    }
                }
            }
            return true;
        }
    };
    TwoSet solve;
    struct Node
    {
        int x,y;
    };
    Node a[N];
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<m;i++){
                scanf("%d%d",&a[i].x,&a[i].y);
                if(a[i].x>a[i].y)
                    swap(a[i].x,a[i].y);
            }
            solve.init(m);
            for(int i=0;i<m;i++)
            {
                if(abs(a[i].x-a[i].y)==1)
                    continue;
                for(int j=i+1;j<m;j++)
                {
                    if(abs(a[j].x-a[j].y)==1)
                        continue;
                    if( (a[i].x>a[j].x && a[i].y>a[j].y) || (a[i].x<a[j].x && a[i].y<a[j].y)  )
                        solve.add_Node(i,j);
                }
            }
            if(solve.yougth(m))
                puts("panda is telling the truth...");
            else
                puts("the evil panda is lying again");
        }
        return 0;
    }

[poj 3207 Ikki_s Story IV - Panda_s Trick]: http://poj.org/problem?id=3207