CUGB OJ(coj) 1253 2-sat

发布时间:2016-12-11 2:59:46 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"CUGB OJ(coj) 1253 2-sat",主要涉及到CUGB OJ(coj) 1253 2-sat方面的内容,对于CUGB OJ(coj) 1253 2-sat感兴趣的同学可以参考一下。

传送门 题意:中文,自己看。 思路:二分枚举影响值,看在该值时能否不引起冲突。 刚刚学2-sat,很神奇,各种不会。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define maxn 1<<30 using namespace std; struct nod { int a,b,c; } p[100000]; int n,m,ans,cnt,s[100000]; int fst[100000],next[1000005],node[1000005],en; bool v[100000]; void add(int x,int y) { next[++en]=fst[x]; fst[x]=en; node[en]=y; } void build(int x) { en=0; memset(fst,-1,sizeof(fst)); for(int i=0;i<m;i++) { if(p[i].c>x) { add(2*(p[i].a-1),2*(p[i].b-1)+1); add(2*(p[i].a-1)+1,2*(p[i].b-1)); add(2*(p[i].b-1),2*(p[i].a-1)+1); add(2*(p[i].b-1)+1,2*(p[i].a-1)); } } } bool dfs(int x) { if(v[x^1])return false; if(v[x])return true; v[x]=1; s[cnt++]=x; for(int i=fst[x];i!=-1;i=next[i]) { if(!dfs(node[i]))return false; } return true; } bool twosat() { memset(v,0,sizeof(v)); for(int j=0; j<n; j++) { if(!v[2*j]&&!v[2*j+1]) { cnt=0; if(!dfs(2*j)) { while(cnt>0)v[s[--cnt]]=0; if(!dfs(2*j+1))return false; } } } return true; } void solve() { int l=0,r=maxn,mid; while(l<=r) { mid=(l+r)/2; build(mid); if(twosat()) { r=mid-1; ans=min(ans,mid); } else l=mid+1; } } int main() { scanf("%d%d",&n,&m); for(int i=0; i<m; i++) { scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c); } ans=maxn; solve(); cout<<ans<<endl; return 0; }

上一篇:PhotoSwipe简介
下一篇:hdu4620 Fruit Ninja Extreme

相关文章

相关评论