首页 > 代码库 > POJ-3207-Ikki's Story IV - Panda's Trick(2-sat模板)
POJ-3207-Ikki's Story IV - Panda's Trick(2-sat模板)
2-sat模板提。
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<map> #include<queue> #include<vector> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) #define INF 0x3f3f3f3f typedef long long LL; using namespace std; const int maxn=1005; const int maxm=2000005; int first[maxn],ecnt,u[maxm],v[maxm],nex[maxm]; int low[maxn],dfn[maxn],stck[maxn],belong[maxn]; int indx,top,scc; bool ins[maxn]; int num[maxn]; int n,m; int a[maxn],b[maxn]; void tarjan(int u) { low[u]=dfn[u]=++indx; stck[top++]=u; ins[u]=1; for(int e=first[u];~e;e=nex[e]) { if(!dfn[v[e]]) { tarjan(v[e]); low[u]=min(low[u],low[v[e]]); } else if(ins[v[e]])low[u]=min(low[u],dfn[v[e]]); } if(low[u]==dfn[u]) { int v; scc++; do { v=stck[--top]; ins[v]=false; belong[v]=scc; num[scc]++; }while(v!=u); } } void solve(int n) { clr(dfn,0); clr(ins,0); clr(num,0); indx=scc=top=0; for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); } void add_(int a,int b) { u[ecnt]=a; v[ecnt]=b; nex[ecnt]=first[a]; first[a]=ecnt++; } void init() { ecnt=0; clr(first,-1); } inline bool pan(int a,int b,int c,int d) { return (a<b&&b<c&&c<d)||(d<c&&c<b&&b<a); } int main() { while(~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]); } init(); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(pan(a[i],a[j],b[i],b[j])){ add_(i,j+m); add_(j,i+m); add_(i+m,j); add_(j+m,i); } solve(2*m); int ans=1; for(int i=1;i<=m&&ans;i++) if(belong[i]==belong[i+m])ans=0; if(ans)puts("panda is telling the truth..."); else puts("the evil panda is lying again"); } return 0; }
POJ-3207-Ikki's Story IV - Panda's Trick(2-sat模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。