算法：POJ 3207 Ikki's Story IV

【题目大意】

一个圆圈上有N个数：0，1，2……N-1。 然后有m条线两两连接这些点，这些线可 以在圆圈里面，也可以在圆圈外面。问有没有一种方式，使得这些线都不相交。

【思路】

以 线为单位，每条线要么在圆圈里面，要么在圆圈外面，典型的2-SAT模型。

【代码】

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;  

typedef long long int64;  

const int MAXN = 1010;
const int VN   = MAXN*2;
const int EN   = VN*VN/2;
int n, m;
int arr[VN][2];  

struct Graph{
    int size;
    int head[VN];
    struct{
        int v, next;
    }E[EN];  

    void init(){
        size = 0;
        memset(head, -1, sizeof(head));
    }
    void addEdge(int u, int v){
        E[size].v = v;
        E[size].next = head[u];
        head[u] = size++;
    }
}g;  

class Two_Sat{
public:
    bool check(const Graph& g, const int n){
        scc(g, n);
        for(int i=0; i<n; ++i)
            if(belong[i] == belong[i+n])
                return false;
        return true;
    }
private:
    void tarjan(const Graph& g, const int u){
        int v;
        DFN[u] = low[u] = ++idx;
        sta[top++] = u;
        instack[u] = true;  

        for(int e=g.head[u]; e!=-1; e=g.E[e].next){
            v = g.E[e].v;
            if(DFN[v] == -1){
                tarjan(g, v);
                low[u] = min(low[u], low[v]);
            }else if(instack[v]){
                low[u] = min(low[u], DFN[v]);
            }
        }  

        if(DFN[u] == low[u]){
            ++bcnt;
            do{
                v = sta[--top];
                instack[v] = false;
                belong[v] = bcnt;
            }while(u != v);
        }
    }  

    void scc(const Graph& g, const int n){
        idx = top = bcnt = 0;
        memset(DFN, -1, sizeof(DFN));
        memset(instack, 0, sizeof(instack));
        for(int i=0; i<2*n; ++i)
            if(DFN[i] == -1)
                tarjan(g, i);
    }
private:
    int idx, top, bcnt;
    int DFN[VN];
    int low[VN];
    int sta[VN];
    int belong[VN];
    bool instack[VN];  

}sat;  

bool isCross(int* A, int *B){
    return  A[0]>B[0]&&A[0]<B[1] && (A[1]<B[0] || A[1]>B[1])
         || A[1]>B[0]&&A[1]<B[1] && (A[0]<B[0] || A[0]>B[1]);
}  

int main(){
    while(~scanf("%d%d", &n, &m)){  

        g.init();
        for(int i=0; i<n; ++i){
            scanf("%d%d", &arr[i][0], &arr[i][1]);
            if(arr[i][0] > arr[i][1]) swap(arr[i][0], arr[i][1]);
        }  

        for(int i=0; i<n; ++i){
            for(int j=i+1; j<n; ++j){
                if(isCross(arr[i], arr[j])) {
                    g.addEdge(i, j+n);
                    g.addEdge(i+n, j);
                    g.addEdge(j, i+n);
                    g.addEdge(j+n, i);
                }
            }
        }
        if(sat.check(g, n)) puts("panda is telling the truth...");
        else puts("the evil panda is lying again");  

    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， const
， head
， size
圆圈
marty s story、gelei s story、what s your story、the invalids story、tfamily s story，以便于您获取更多的相关知识。