zoj3422Go Deeper(2-sat + 二分)
题目请戳这里
题目大意：
#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 405;const int M = 10005;struct node{ int to,next;}g[M];int head[N],stack1[N],stack2[N],vis[N],scc[N];int n,m,num;bool flag;int a[M],b[M],c[M];void init(){ memset(head,-1,sizeof(head)); flag = true; memset(vis,0,sizeof(vis)); memset(scc,0,sizeof(scc)); stack1[0] = stack2[0] = 0; num = 0;}void build(int s,int e){ g[num].to = e; g[num].next = head[s]; head[s] = num ++;}void dfs(int cur,int &sig,int &cnt){ if(flag == false) 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].to]) dfs(g[i].to,sig,cnt); else { if(scc[g[i].to] == 0) while(vis[stack2[stack2[0]]] > vis[g[i].to]) stack2[0] --; } } if(stack2[stack2[0]] == cur) { stack2[0] --; cnt ++; do { scc[stack1[stack1[0]]] = cnt; if(scc[stack1[stack1[0]]^1] == cnt) { flag = false; return; } }while(stack1[stack1[0] --] != cur); }}void Gabow(){ int i,sig,cnt; sig = cnt = 0; for(i = 0;i < n + n && flag;i ++) if(!vis[i]) dfs(i,sig,cnt);}void solve(){ int l,r,mid; int ans,i; l = 0;r = m; while(l <= r) { mid = (l + r)>>1; init(); for(i = 0;i < mid;i ++) { int u = a[i]<<1; int v = b[i]<<1; if(c[i] == 0)// !=0 { build(u,v^1); build(v,u^1); } if(c[i] == 1)// != 1 { build(u,v); build(v,u); build(u^1,v^1); build(v^1,u^1); } if(c[i] == 2)// != 2 { build(u^1,v); build(v^1,u); } } Gabow(); if(flag) { ans = mid; l = mid + 1; } else r = mid - 1; } printf("%d\n",ans);}int main(){ int i,t; scanf("%d",&t); while(t --) { scanf("%d%d",&n,&m); for(i = 0;i < m;i ++) scanf("%d%d%d",&a[i],&b[i],&c[i]); solve(); } return 0;}