题意：
有\(n\)个布尔变量\(x_i\)，有一个递归函数。如果满足条件\(x[a[dep]] + x[b[dep]] \neq c[dep]\)，那么就再往深递归一层。
问最多能递归多少层。
分析：
首先二分能递归的深度，然后在2-SAT中添加相应的约束条件。
约束条件是这样添加的，对于两个布尔变量\(x\)和\(y\)：
- \(x+y \neq 0 \Rightarrow x \vee y\)
- \(x+y \neq 1 \Rightarrow \bar{x} \vee y, x \vee \bar{y}\)
- \(x+y \neq 2 \Rightarrow \bar{x} \vee \bar{y}\)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 200 + 10;
struct TwoSAT
{
int n;
vector<int> G[maxn * 2];
bool mark[maxn * 2];
int S[maxn * 2], c;
bool dfs(int x) {
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x] = true;
S[c++] = x;
for(int i = 0; i < G[x].size(); i++)
if(!dfs(G[x][i])) return false;
return true;
}
void init(int n) {
this->n = n;
for(int i = 0; i < n * 2; i++) G[i].clear();
memset(mark, false, sizeof(mark));
}
void add_clause(int x, int xval, int y, int yval) {
x = x * 2 + xval;
y = y * 2 + yval;
G[x^1].push_back(y);
G[y^1].push_back(x);
}
bool solve() {
for(int i = 0; i < n * 2; i += 2)
if(!mark[i] && !mark[i+1]) {
c = 0;
if(!dfs(i)) {
while(c > 0) mark[S[--c]] = false;
if(!dfs(i+1)) return false;
}
}
return true;
}
}solver;
const int maxm = 10000 + 10;
int n, m;
int a[maxm], b[maxm], c[maxm];
bool check(int dep) {
solver.init(n);
for(int i = 0; i < dep; i++) {
if(c[i] == 0) {
solver.add_clause(a[i], 1, b[i], 1);
}
else if(c[i] == 1) {
solver.add_clause(a[i], 1, b[i], 0);
solver.add_clause(a[i], 0, b[i], 1);
}
else solver.add_clause(a[i], 0, b[i], 0);
}
return solver.solve();
}
int main()
{
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) scanf("%d%d%d", a + i, b + i, c + i);
int L = 0, R = m;
while(L < R) {
int mid = (L + R) / 2 + 1;
if(check(mid)) L = mid;
else R = mid - 1;
}
printf("%d\n", L);
}
return 0;
}