链接
http://acm.hdu.edu.cn/showproblem.php?pid=3715
题意
数组 $x$ 为 $0\sim n$ 的取值，每个数只有 $0,1$ 两种取值
数组 $a,b$ 取值为 $0\sim n$
数组 $c$ 取值为 $0,1,2$
有 $m$ 个不等式，$x_{a_i}+x_{b_i}\ne c_i$
给数组 $x$ 赋值，问最多能满足前多少个不等式
思路
2 - SAT
根据不等式得出取值限制
$x_{a_i}=0\rightarrow x_{b_i}=1$
$x_{b_i}=0\rightarrow x_{a_i}=1$
$x_{a_i}=0\rightarrow x_{b_i}=0$
$x_{a_i}=1\rightarrow x_{b_i}=1$
$x_{b_i}=0\rightarrow x_{a_i}=0$
$x_{b_i}=1\rightarrow x_{a_i}=1$
$x_{a_i}=1\rightarrow x_{b_i}=0$
$x_{b_i}=1\rightarrow x_{a_i}=0$
二分 $m$ 建图，判断是否矛盾
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=405;
const int M=10005;
vector<int> G[N];
int n,m,cnt,dfn[N],low[N],top,stk[N],cnt_scc,c[N];
int a[M],b[M],d[M];
bool ins[N];
void init() {
for(int i=0;i<n*2;i++) G[i].clear();
cnt=cnt_scc=top=0;
for(int i=0;i<n*2;i++) dfn[i]=low[i]=c[i]=0,ins[i]=false;
}
void tarjan(int u) {
dfn[u]=low[u]=++cnt;
stk[++top]=u;
ins[u]=true;
for(auto v:G[u]) {
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
++cnt_scc;
int x;
do {
x=stk[top--];
ins[x]=false;
c[x]=cnt_scc;
} while(u!=x);
}
}
bool check(int mid) {
init();
for(int i=1;i<=mid;i++) {
if(d[i]==0) {
G[a[i]<<1].PB((b[i]<<1)+1);
G[b[i]<<1].PB((a[i]<<1)+1);
}
else if(d[i]==1) {
G[a[i]<<1].PB(b[i]<<1);
G[(a[i]<<1)+1].PB((b[i]<<1)+1);
G[b[i]<<1].PB(a[i]<<1);
G[(b[i]<<1)+1].PB((a[i]<<1)+1);
}
else {
G[(a[i]<<1)+1].PB(b[i]<<1);
G[(b[i]<<1)+1].PB(a[i]<<1);
}
}
for(int i=0;i<2*n;i++) if(!dfn[i]) tarjan(i);
for(int i=0;i<n;i++) if(c[i<<1]==c[(i<<1)+1]) return false;
return true;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&d[i]);
int l=0,r=m;
while(l<r) {
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
return 0;
}
|