首页 > 代码库 > POJ Ikki's Story IV - Panda's Trick [2-SAT]
POJ Ikki's Story IV - Panda's Trick [2-SAT]
题意：
圆上n个点，m对点之间连边，连在园内或园外，所有边不相交是否可行
发现两对点连线都在内相交则都在外也相交，那么只有一个在内一个在外啦，转化为$2-SAT$问题
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=1005,M=5e5;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,a[N],b[N];struct edge{ int v,ne;}e[M];int h[N],cnt=0;inline void ins(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;}void buildGraph(){ for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if((a[i]<a[j]&&a[j]<b[i]&&b[i]<b[j])||(a[j]<a[i]&&a[i]<b[j]&&b[j]<b[i])){ int x=i<<1,y=j<<1; ins(x,y-1);ins(y-1,x); ins(x-1,y);ins(y,x-1); } }int dfn[N],low[N],dfc,belong[N],scc;int st[N],top;void dfs(int u){ dfn[u]=low[u]=++dfc; st[++top]=u; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ dfs(v); low[u]=min(low[u],low[v]); }else if(!belong[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]){ scc++; while(true){ int x=st[top--]; belong[x]=scc; if(x==u) break; } }}bool judge(){ for(int i=1;i<=m;i++) if(belong[i<<1]==belong[(i<<1)-1]) return false; return true;}int main(){ freopen("in","r",stdin); n=read();m=read(); for(int i=1;i<=m;i++){ a[i]=read(),b[i]=read(); if(a[i]>b[i]) swap(a[i],b[i]); } buildGraph(); int _=m<<1; for(int i=1;i<=_;i++) if(!dfn[i]) dfs(i); if(judge()) puts("panda is telling the truth..."); else puts("the evil panda is lying again");}
POJ Ikki's Story IV - Panda's Trick [2-SAT]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。