本文共 926 字，大约阅读时间需要 3 分钟。

【题目链接】

【题目大意】

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

【思路】

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

【代码】

#include
   
     #include
    
     #include
     
      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
      
       B[0]&&A[0]
       
        B[1])         || A[1]>B[0]&&A[1]
        
         B[1]);}int main(){ while(~scanf("%d%d", &n, &m)){ g.init(); for(int i=0; i
         
           arr[i][1]) swap(arr[i][0], arr[i][1]); } for(int i=0; i
         
        
       
      
     
    
   

转载地址：http://dpzni.baihongyu.com/