首页 > 代码库 > HDU3715(二分+2-SAT)
HDU3715(二分+2-SAT)
题意就是求满足题目中给出的递归代码的最大递归层数。
由于x[i]只有0和1,所以我们就比较容易想到2-SAT,然后二分递归层数,求出满足要求的最大递归层数。建图的时候,不满足不等式的就是互相矛盾的,然后建边。
#include <stdio.h> #include <string.h> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <map> #include <queue> #include <stack> #include <set> #define M 40500 #define LL long long #define Ld __int64 #define eps 0.00001 #define INF 999999999 #define MOD 112233 #define MAX 26 using namespace std; vector<int> G[M]; int dfn[M],low[M],sccno[M],scc_cnt; int indx; stack<int> s; void Tarjan(int u) { indx++; dfn[u]=low[u]=indx; s.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) { scc_cnt++; for(;;) { int x=s.top(); s.pop(); sccno[x]=scc_cnt; if(x==u) break; } } } void find_scc(int n) { indx=scc_cnt=0; memset(dfn,0,sizeof(dfn)); memset(sccno,0,sizeof(sccno)); for(int i=0;i<n;i++) if(!dfn[i]) Tarjan(i); } int a[M],b[M],c[M]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); } int l=0,r=m+1; while(l<r) { for(int i=0;i<n*2;i++) G[i].clear(); int mid=(l+r)>>1; for(int i=0;i<mid;i++) { int k=a[i]<<1; int p=b[i]<<1; if(c[i]==0) //至少有一个为1 { G[k].push_back(p^1); //k为0时,p^1一定为1 G[p].push_back(k^1); } else if(c[i]==1) //全为0或全为1 { G[k].push_back(p); G[p].push_back(k); G[k^1].push_back(p^1); G[p^1].push_back(k^1); } else //最多有一个为1 { G[k^1].push_back(p); //k^1为1时,p一定为0 G[p^1].push_back(k); } } find_scc(n*2); int flag=0; for(int i=0;i<n*2;i+=2) { if(sccno[i]==sccno[i^1]) { flag=1; break; } } if(flag) { r=mid; } else { l=mid+1; } } printf("%d\n",r-1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。