POJ3297【2-SAT一水】
题意理解有问题。 以为是是否存在相交直线了。 忽略了可以在圆外部连的情况。
自己有心理阴影了。 读题有心理阴影了肿么破。 呵~~~~~~~~~~
正解。 2-SAT一水。
我老是感觉这题与2-SAT不太相关。。
这题是必须同为真或同为假。 不像2-SAT的1为真或2为真。 并且里面连线之后外面照常可以连。 囧 ，难道又是破题意有误？
行了，直接题解吧，被题意坑坏了。
果然，考虑点是不满足2-SAT的条件，可是可以考虑边。。。囧了。。。。。。 是否是可析取或可以加条件。
AC了。。
思路过程： 1.直接暴力，题意理解是只能所有线段都在园内或圆外， WA
2.后来试了几次感觉好像题意理解有问题， 只看了题意，原来可以“曲”在圆外。
3.试了试2-SAT以点为判断 感觉与2-SAT相应条件不符 WA+++
4.参考了一下解题报告，可以枚举边的2-SAT思路，好像会了，顺便对2-SAT LRJ版稍微理解了点。
5.AC 别人的2-SAT模板（仅网上）一般都是用tarjan判断是否有i,i+1在同一个连通分量里面。 LRJ的代码其实也类似思路。
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;const int maxn=1005;int n;vector<int> G[maxn*2];bool mark[maxn*2];int s[maxn*2],c;struct xx{ int be,en;}x[5555];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(){ for(int i=0;i<n*2;i++) G[i].clear(); memset(mark,0,sizeof(mark));}void add(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);}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;}bool judge(int a,int b,int c,int d){ if((a<c&&c<b&&b<d)||(c<a&&a<d&&d<b)) return true; else return false;}int main(){ int m,a,b; scanf("%d%d",&n,&m); init(); for(int i=0;i<m;i++) { scanf("%d%d",&x[i].be,&x[i].en); if(x[i].be>x[i].en) swap(x[i].be,x[i].en); } for(int i=0;i<m;i++) for(int j=i+1;j<m;j++) { if(judge(x[i].be,x[i].en,x[j].be,x[j].en)) { G[i*2].push_back(j*2+1); G[j*2].push_back(i*2+1); G[i*2+1].push_back(j*2); G[j*2+1].push_back(i*2); } } if(solve()==true) printf("panda is telling the truth...\n"); else printf("the evil panda is lying again\n"); return 0;}