首页 > 代码库 > HDU 3062

HDU 3062

2024-07-12 20:58:01   219人阅读

2-SAT问题

有必要写一下<i,j>边的含义。所谓，选i必选j的意思是，因为每一对中只能有一个被选，则矛盾的对中若其中一被选i，另一个不可能是j‘，因为存在矛盾，所以必选 j.

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5  6 using namespace std; 7  8 const int MAXN=2100; 9 const int MAXM=1000000;10 11 int head[MAXN],stack[MAXN],dfn[MAXN],low[MAXN];12 int belong[MAXN],pat;13 int st[MAXN],stop;14 15 struct {16     int u,v;17     int next;18 }edge[MAXM];19 int n,m,tot,index;20 21 void init(){22     memset(head,-1,sizeof(head));23     for(int i=0;i<=2*n;i++){24         dfn[i]=low[i]=0;25         belong[i]=-1;26         stack[i]=0;27     }28 }29 30 void addedge(int u,int v){31     edge[tot].u=u;32     edge[tot].v=v;33     edge[tot].next=head[u];34     head[u]=tot++;35 }36 37 void tarjan(int u){38     int v;39     dfn[u]=low[u]=++index;40     st[stop++]=u; stack[u]=1;41     for(int e=head[u];e!=-1;e=edge[e].next){42         v=edge[e].v;43         if(dfn[v]==0){44             tarjan(v);45             low[u]=min(low[u],low[v]);46         }47         else if(stack[v]==1){48             low[u]=min(low[u],dfn[v]);49         }50     }51     if(dfn[u]==low[u]){52         pat++;53         do{54             v=st[--stop];55             stack[v]=0;56             belong[v]=pat;57         }while(u!=v);58     }59 }60 61 int main(){62     int a1,a2,b1,b2;63     while(scanf("%d",&n)!=EOF){64         init();65         tot=0; index=0;66         pat=-1; stop=0;67         scanf("%d",&m);68         for(int i=1;i<=m;i++){69             scanf("%d%d%d%d",&a1,&a2,&b1,&b2);70             addedge(2*a1+b1,((2*a2+b2)^1));71             addedge(2*a2+b2,((2*a1+b1)^1));72         }73         for(int i=0;i<2*n;i++){74             if(dfn[i]==0)75             tarjan(i);76         }77         bool flag=false;78         for(int i=0;i<n;i++){79             if(belong[2*i]==belong[2*i+1]){80                 printf("NO\n");81                 flag=true;82                 break;83             }84         }85         if(!flag){86             printf("YES\n");87         }88     }89     return 0;90 }
View Code


联系
我们