HDOJ 3715 - Go Deeper 二分+2-sat判断

网友投稿 558 2022-10-20

HDOJ 3715 - Go Deeper 二分+2-sat判断

HDOJ 3715 - Go Deeper 二分+2-sat判断

题意:

有这么一个过程:

go(int dep, int n, int m) begin output the value of dep. if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m) end

其中x[]的值为0或1...c[]的值为0或1或2....现在告诉a[],b[],c[]..问这个过程最深可能是多少？

题解

看这个过程..实际上当在m层没办法下去了.更深的层肯定也到不了了...所以满足单调性...先读入a[],b[],c[]...再二分M...构图..2-sat..tarjan判断....

Program:

#include#include#include#include#include#include#include#include#include#define oo 1000000007#define MAXN 50005<<1#define MAXM 500005<<1#define ll long longusing namespace std; struct node{ int y,next;}line[MAXM];int A[MAXN],B[MAXN],C[MAXN],Lnum,_next[MAXN],dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex; bool instack[MAXN];stack mystack;void addline(int x,int y){ line[++Lnum].next=_next[x],_next[x]=Lnum,line[Lnum].y=y;}void tarjan(int x){ mystack.push(x),instack[x]=true; dfn[x]=low[x]=++DfsIndex; for (int k=_next[x];k;k=line[k].next) { int y=line[k].y; if (!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); }else if (instack[y]) low[x]=min(low[x],dfn[y]); } if (low[x]==dfn[x]) { tpnum++; do { x=mystack-(); mystack.pop(); tp[x]=tpnum; instack[x]=false; }while (low[x]!=dfn[x]); }}bool _2sat(int N,int M){ int i; Lnum=0; memset(_next,0,sizeof(_next)); for (i=1;i<=M;i++) { int a=A[i],b=B[i],c=C[i]; if (!c) addline(a<<1,b<<1|1),addline(b<<1,a<<1|1); else if (c==1) { addline(a<<1,b<<1),addline(a<<1|1,b<<1|1); addline(b<<1,a<<1),addline(b<<1|1,a<<1|1); } else if (c==2) addline(a<<1|1,b<<1),addline(b<<1|1,a<<1); } while (!mystack.empty()) mystack.pop(); memset(dfn,0,sizeof(dfn)); memset(instack,false,sizeof(instack)); DfsIndex=tpnum=0; for (i=0;i<(N<<1);i++) if (!dfn[i]) tarjan(i); for (i=0;i1) { mid=l+r>>1; if (_2sat(N,mid)) l=mid; else r=mid; } printf("%d\n",l); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：判断
上一篇:异步协程框架,SOA服务化调用，支持并行、串行调用、请求合并
下一篇:小程序docker（小程序开发哪家好?）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~