hdu 4115 Eliminate the Conflict （ 2-sat ）

Eliminate the ConflictTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1315    Accepted Submission(s): 563

Problem DescriptionInputOutputSample InputSample OutputSource#include <cstdio>#include <cstring>#define maxn 20005#define MAXN 100005using namespace std;int n,m,num,flag;int bob[maxn];int head[maxn];int scc[maxn];int vis[maxn];int stack1[maxn];int stack2[maxn];struct edge{ int v,next;} g[MAXN];int a[4][2]={ 0,0, 1,2, 2,3, 1,3};void init(){ memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(scc,0,sizeof(scc)); stack1[0] = stack2[0] = num = 0; flag = 1;}void addedge(int u,int v){ num++; g[num].v = v; g[num].next = head[u]; head[u] = num;}void dfs(int cur,int &sig,int &cnt){ if(!flag) return; vis[cur] = ++sig; stack1[++stack1[0]] = cur; stack2[++stack2[0]] = cur; for(int i = head[cur]; i; i = g[i].next) { if(!vis[g[i].v]) dfs(g[i].v,sig,cnt); else { if(!scc[g[i].v]) { while(vis[stack2[stack2[0]]] > vis[g[i].v]) stack2[0] --; } } } if(stack2[stack2[0]] == cur) { stack2[0] --; ++cnt; do { scc[stack1[stack1[0]]] = cnt; int tmp = stack1[stack1[0]]; if((tmp >n && scc[tmp - n] == cnt) || (tmp <= n && scc[tmp + n] == cnt)) // 注意这里的‘=’号 { flag = false; return; } } while(stack1[stack1[0] --] != cur); }}void Twosat(){ int i,sig,cnt; sig = cnt = 0; for(i=0; i<n+n&&flag; i++) { if(!vis[i]) dfs(i,sig,cnt); }}int main(){ int i,j,t,u,v,k,test=0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); num=0; for(i=1; i<=n; i++) { scanf("%d",&bob[i]); } for(i=1; i<=m; i++) { scanf("%d%d%d",&u,&v,&k); if(k) { if(a[bob[u]][0]==a[bob[v]][0]) addedge(u,v+n),addedge(v,u+n); if(a[bob[u]][0]==a[bob[v]][1]) addedge(u,v),addedge(v+n,u+n); if(a[bob[u]][1]==a[bob[v]][0]) addedge(u+n,v+n),addedge(v,u); if(a[bob[u]][1]==a[bob[v]][1]) addedge(u+n,v),addedge(v+n,u); } else { if(bob[u]==bob[v]) { addedge(u,v); addedge(v,u); addedge(u+n,v+n); addedge(v+n,u+n); } else { //注意这里 只能唯一的选择一条边等价于不能选其他边 if(a[bob[u]][0]==a[bob[v]][0]) addedge(u+n,u),addedge(v+n,v); if(a[bob[u]][0]==a[bob[v]][1]) addedge(u+n,u),addedge(v,v+n); if(a[bob[u]][1]==a[bob[v]][0]) addedge(u,u+n),addedge(v+n,v); if(a[bob[u]][1]==a[bob[v]][1]) addedge(u,u+n),addedge(v,v+n); } } } Twosat(); printf("Case #%d: ",++test); if(flag) printf("yes\n"); else printf("no\n"); } return 0;}