http://poj.org/problem?id=3207
一个圆上有n个点 m条连线(一个点最多只能连一条)
每条线可以走圆外 或 圆内 2-SAT问题
把每条边转化为两条即为A 和 A‘ 他们只能出现一个 然后把相交的直线视为 相斥 这样就转化成简单的2-SAT问题了
代码及其注释:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<map> #include<queue> #include<stack> #include<cmath> #define LL long long using namespace std; const int N=10005; struct node { struct tt *next; }mem[N]; struct tt { int j; struct tt *next; }; struct ss { int l1,l2; }side[N]; int dfn[N]; int low[N]; bool in[N]; bool visited[N]; int deep; int f[N]; stack<int>str; void build(int i,int j) { struct tt *t=new tt; t->j=j; t->next=mem[i].next; mem[i].next=t; } void Dele(int n) { for(int i=0;i<=n;++i) mem[i].next=NULL; } bool X(int i,int j)//判断两边是否相交 l2>l1 { if(side[i].l1>side[j].l1&&side[i].l1<side[j].l2&&side[i].l2>side[j].l2) return true; if(side[j].l1>side[i].l1&&side[j].l1<side[i].l2&&side[j].l2>side[i].l2) return true; return false; } void Tarjan(int x)//求环加缩点 { visited[x]=true; str.push(x); in[x]=true; dfn[x]=low[x]=deep++; struct tt *t=mem[x].next; while(t!=NULL) { if(visited[t->j]==false) { Tarjan(t->j); low[x]=min(low[x],low[t->j]); }else if(in[t->j]==true) { low[x]=min(low[x],dfn[t->j]); } t=t->next; } if(low[x]==dfn[x]) { while(str.top()!=x) { int k=str.top(); str.pop(); in[k]=false; f[k]=x; } int k=str.top(); str.pop(); in[k]=false; f[k]=x; } } int main() { //freopen("data.txt","r",stdin); int n,m; while(scanf("%d %d",&n,&m)!=EOF) { for(int i=0;i<m;++i) { scanf("%d %d",&side[i].l1,&side[i].l2); if(side[i].l1>side[i].l2) swap(side[i].l1,side[i].l2); for(int j=0;j<i;++j) { if(X(i,j)) { build(j,i+m);//相斥建边 build(i,j+m); build(j+m,i); build(i+m,j); } } } while(!str.empty()) str.pop(); memset(dfn,-1,sizeof(dfn)); memset(low,-1,sizeof(low)); memset(in,false,sizeof(in)); memset(visited,false,sizeof(visited)); deep=0; for(int i=0;i<m*2;++i) { if(visited[i]==false)//遍历 Tarjan(i); } int l; for(l=0;l<m;++l) if(f[l]==f[l+m])//一个对应属于同一个环 则break break; if(l<m) printf("the evil panda is lying again\n"); else printf("panda is telling the truth...\n"); Dele(2*m); } return 0; }