zoj 3422 Go Deeper （ 二分+2-sat ）

Here is a procedure's pseudocode:

	   go(int dep, int n, int m)  
	   begin  
	      output the value of dep. 
	      if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
	   end 
	 

In this code n is an integer. a, b, c and x are 4 arrays of integers. The index of array always starts from 0. Array a and b consist of non-negative integers smaller than n. Arrayx consists of only 0 and 1. Array c consists of only 0, 1 and 2. The lengths of arraya, b and c are m while the length of array x is n.

Given the elements of array a, b, and c, when we call the procedure go(0,n , m) what is the maximal possible value does the procedure output

Input

There are multiple test cases. The first line of input is an integer T (0 <T ≤ 100), indicating the number of test cases. Then T test cases follow. Each case starts with a line of 2 integersn and m (0 < n ≤ 200, 0 < m ≤ 10000). Then m lines of 3 integers follow. Thei-th(1 ≤ i ≤ m) line of them are a_i-1 ,b_i-1 andc_i-1 (0 ≤ a_i-1, b_i-1 <n, 0 ≤ c_i-1 ≤ 2).

Output

For each test case, output the result in a single line.

Sample Input

3
2 1
0 1 0
2 1
0 0 0
2 2
0 1 0
1 1 2

Sample Output

1
1
2

题意：

读一段程序，问怎样取x数组的值使得输出的dep最大。

思路：

要使dep最大，则要尽量满足 x[a[dep]] + x[b[dep]] != c[dep] ，x只有两种取值，很快想到2-sat模型，二分答案，根据c的值建好图，看是否满足条件就够了。

代码：

#include 
  
   
#include 
   
     #define maxn 405 #define MAXN 200005 using namespace std; int n,m,num,flag,ans; int head[maxn]; int scc[maxn]; int vis[maxn]; int stack1[maxn]; int stack2[maxn]; int a[MAXN],b[MAXN],c[MAXN]; struct edge { int v,next; } g[MAXN]; 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
    
     >1; if(isok(mid)) le=mid; else ri=mid-1; } ans=le+1; } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0; i