题目类型 2-SAT
题目意思
有一个从 0 -> n-1(n <= 1000) 的数字圆环 现在给出 m 条边(m <= 500) 其中一条边(u,v)的意思是把 u 点和 v 点连起来 (显然有两种方法 一种是在
圆环里面连 一种是在外面连) 问是否有一种连线的方法使所有边都不相交
解题方法
很明显的 2-SAT 问题 对于两条边 判断一下当用同一种方法进行连接时会不会冲突 例如 (0,2)和(1,3)如果都是在圆内连或者都是在圆外连两条线就会相交,令布尔变量 xi 表示第 i 条线是否在圆内连接 这时如果第 i 条边和第 j 条边冲突的话
不能同时满足 xi == false && xj == false 即 xi == true || xj == true
不能同时满足 xi == true && xj == true 即 xi == false || xj == false
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 1000 + 10; int a[maxn][2]; struct TwoSet { int n; vector<int>G[maxn*2]; bool mark[maxn*2]; int S[maxn*2], c; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x] = true; S[c++] = x; for( int i=0; i<G[x].size(); i++ ) { if(!dfs(G[x][i])) return false; } return true; } void init(int n) { this->n = n; for( int i=0; i<n*2; i++ ) G[i].clear(); memset(mark, 0, sizeof(mark)); } void add_clause(int x, int xval, int y, int yval) { // 建图 x=xval or y = yval is true x = x * 2 + xval; y = y * 2 + yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve() { for( int i=0; i<n*2; i+=2 ) { if(!mark[i] && !mark[i+1] ) { c = 0; if(!dfs(i)) { while(c > 0) mark[S[--c]] = false; if(!dfs(i+1)) return false; } } } return true; } }s; int main() { freopen("in","r", stdin); int n, m; while(scanf("%d%d", &n, &m) != EOF) { s.init(m); for( int i=0; i<m; i++ ) { scanf("%d%d", &a[i][0], &a[i][1]); } for( int i=0; i<m; i++ ) { for( int j=i+1; j<m; j++ ) { if((a[i][0]>a[j][0]&&a[i][0]<a[j][1]&&a[i][1]>a[j][1])||(a[i][0]<a[j][0]&&a[i][1]>a[j][0]&&a[i][1]<a[j][1])) { s.add_clause(i, 0, j, 0); // x == 0 || y == 0 s.add_clause(i, 1, j, 1); // x == 1 || y == 1 //printf("i = %d j = %d\n",i+1,j+1); } } } bool ans = s.solve(); if(ans) printf("panda is telling the truth...\n"); else printf("the evil panda is lying again\n"); } return 0; }