首页 > 代码库 > POJ 3207 Ikki's Story IV - Panda's Trick
POJ 3207 Ikki's Story IV - Panda's Trick
2-SAT判可行。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxv 1050#define maxe 200500using namespace std;int n,m,a[maxv],b[maxv],g[maxv],nume=0,bel[maxv],dfn[maxv],low[maxv],times=0,cnt=0;int stack[maxv],top=0;bool vis[maxv];struct edge{ int v,nxt;}e[maxe];void addedge(int u,int v){ e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume;}bool judge(int x,int y){ if ((a[x]<a[y]) && (a[y]<b[x]) && (b[x]<b[y])) return false; if ((a[y]<a[x]) && (a[x]<b[y]) && (b[y]<b[x])) return false; return true;}void tarjan(int x){ dfn[x]=low[x]=++times;stack[++top]=x;vis[x]=true; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if (vis[v]) low[x]=min(low[x],dfn[v]); } if (low[x]==dfn[x]) { cnt++; int now=0; while (now!=x) { now=stack[top];top--; bel[now]=cnt;vis[now]=false; } }}void get_ans(){ for (int i=1;i<=m;i++) { if (bel[i*2-1]==bel[i*2]) { printf("the evil panda is lying again\n"); return; } } printf("panda is telling the truth...\n");}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&a[i],&b[i]); if (a[i]>b[i]) swap(a[i],b[i]); } for (int i=1;i<=m;i++) for (int j=i+1;j<=m;j++) { if (!judge(i,j)) { addedge(i*2-1,j*2);addedge(j*2,i*2-1); addedge(j*2-1,i*2);addedge(i*2,j*2-1); } } for (int i=1;i<=2*m;i++) if (!dfn[i]) tarjan(i); get_ans(); return 0;}
POJ 3207 Ikki's Story IV - Panda's Trick
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。