首页 > 代码库 > hdu3715 2-sat+二分
hdu3715 2-sat+二分
Go Deeper
题意:确定一个0/1数组(size:n)使得满足最多的条件数。条件在数组a,b,c给出。
吐槽:哎,一水提,还搞了很久!关键是抽象出题目模型(如上的一句话)。以后做二sat:有哪些是点,哪些是条件,分清!,然后注意细节。这次居然因为里面一个小错误:
判断有无解的时候,i与i+1是否在一个SCC中的时候,i居然没有每次+2!而是++!傻X了。。。囧!还一直以为自己二分写错。。。
#include<iostream> #include<cstdio> #include<stack> #include<vector> using namespace std; const int inf=0x3f3f3f3f; const int maxv=402;//maxe=500000; int dfn[maxv];int low[maxv];int vis[maxv];int scc[maxv];int ins[maxv];stack<int>sta; int times=0; int numb=0; vector<vector<int> >e(maxv); void tarjan(int u) { dfn[u]=low[u]=times++; ins[u]=1; sta.push(u); for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(!vis[v]) { vis[v]=1; tarjan(v); if(low[v]<low[u])low[u]=low[v]; } else if(ins[v]&&dfn[v]<low[u]) low[u]=dfn[v]; } if(low[u]==dfn[u]) { numb++; int cur; do{ cur=sta.top(); sta.pop(); ins[cur]=0; scc[cur]=numb; }while(cur!=u); } } int n,m;int a[10005],b[10005],c[10005]; void init() { numb=times=0; for(int i=0;i<maxv;i++) { scc[i]=ins[i]=dfn[i]=low[i]=vis[i]=0; e[i].clear(); } } bool build_solve(int x) { init(); for(int i=0;i<=x;i++) { if(c[i]==2) { e[2*a[i]+1].push_back(2*b[i]); e[2*b[i]+1].push_back(2*a[i]); } else if(c[i]==1) { e[2*a[i]].push_back(2*b[i]); e[2*b[i]].push_back(2*a[i]); e[2*a[i]+1].push_back(2*b[i]+1); e[2*b[i]+1].push_back(2*a[i]+1); } else if(c[i]==0) { e[2*a[i]].push_back(2*b[i]+1); e[2*b[i]].push_back(2*a[i]+1); } } for(int i=0;i<=2*n-1;i++) { if(!vis[i]) { vis[i]=1; tarjan(i); } } for(int i=0;i<=2*n-2;i+=2) //开始写成i++!!!!WA到跪! if(scc[i]==scc[i+1]) return 0; return 1; } void readin() { for(int i=0;i<m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(); readin(); int l=0,r=m,mid; while(l+1<r) { mid=(l+r)/2; if(build_solve(mid)) l=mid; else r=mid; } printf("%d\n",l+1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。