Hdu1824 Let's go home(2-sat)

发布时间:2016-12-6 13:54:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Hdu1824 Let's go home(2-sat)",主要涉及到Hdu1824 Let's go home(2-sat)方面的内容,对于Hdu1824 Let's go home(2-sat)感兴趣的同学可以参考一下。

n个队伍,一个队伍3个人,要求如果队长不在那剩下两个队员必须在,如果剩下两个队员不在队长必须在。m种冲突关系,每种冲突关系中的两个人不能同时存在。问方案是否可行 #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define clr(x)memset(x,0,sizeof(x)) int abs(int x){if(x>0)return x;return -x;} const int maxn=65000; struct node{ int to; int next; }q[1000010]; int head[maxn]; int tot; void add(int s,int u){ q[tot].to=u; q[tot].next=head[s]; head[s]=tot++; } bool ins[maxn]; int color[maxn]; int dfn[maxn],low[maxn],stack[maxn]; int ti,sn,top; void tarjan(int u){ dfn[u]=low[u]=++ti; stack[++top]=u; ins[u]=true; int i,k; for(i=head[u];i;i=q[i].next){ k=q[i].to; if(dfn[k]==0){ tarjan(k); if(low[k]<low[u])low[u]=low[k]; } else if(ins[k]&&dfn[k]<low[u]) low[u]=dfn[k]; } if(dfn[u]==low[u]){ sn++; do{ k=stack[top--]; ins[k]=false; color[k]=sn; }while(k!=u); } } void init(){ clr(low); clr(dfn); clr(ins); clr(head); tot=1; top=-1; sn=ti=0; } int n,m; int main(){ int i,T,a,b,c; while(scanf("%d%d",&T,&m)!=EOF){ init(); n=T*3; for(i=0;i<T;i++){ scanf("%d%d%d",&a,&b,&c); add(a+n,b);add(a+n,c); add(b+n,a);add(c+n,a); } for(i=0;i<m;i++){ scanf("%d%d",&a,&b); add(b,a+n); add(a,b+n); } for(i=0;i<2*n;i++) if(dfn[i]==0)tarjan(i); int flag=0; for(i=0;i<n;i++) if(color[i]==color[i+n])flag=1; if(flag)printf("no\n"); else printf("yes\n"); } return 0; }

上一篇:mvc在视图中使用递归生成树状结构
下一篇:linux gdb core

相关文章

相关评论