CodeChef 2020 November Challenge - Red-Black Boolean Expression

Posted on Edited on In

CodeChef 2020 November Challenge - Red-Black Boolean Expression

吐槽：这题很蠢，很套路

题目大意：

给定 \(n\) 个布尔变量 \(x_i\) ，每个变量有其反变量 \(\overline {x_i}\)

有 \(n\) 组关系 \(a_i,b_i\) ，要求 \(a_i\lor b_i\) 为真

并且保证所有 \(a_i,b_i\) 关系构成一张二分图，其中 \(x_i\) 与 \(\overline{x_i}\) 有一条边相连

给定每个变量的初始值 \(s_i\) ，以及翻转其所需的代价 \(C_i\) ，求最小满足条件的代价

\[ \ \]

\(a_i\lor b_i\) 为真即不存在 \(a_i,b_i\) 均为假的情况

如果是2-sat上的理解，即可以由 \(a_i\) 假推 \(b_i\) 真， \(b_i\) 假推 \(a_i\) 真，但是 \(2-sat\) 没法带权

由于题目保证了关系的二分图性质，不妨把所有变量分成两个集合 \(A,B\)

这个问题令人联想到网络流最小割模型，我们用一条边 \((u,v)\) 限制 \((u,v)\) 不同时为假的情况

对于 \(A\) 中的点，我们令源点 \(S\) 向 \(u\) 连的边 \((S,u,w)\) 表示 \(u\) 变成 \(0\) 所需代价，令 \((u,T,w)\) 表示 \(u\) 变成1的代价

对于 \(B\) 中的点，采取相反的连接方式

任意一个关系的两点不在同一集合，不妨对于 \(u\in A\) 的情况考虑，实际上可以分为两类考虑

  1. \((u,v)\) 不同时为0，那么连接一条边 \((v,u,\infty)\) ，表示如果合法必然有一条让 \(u\) 或 \(v\) 变成1的边被割掉

  2. \((u,v)\) 不同时为1，连接一条边 \((v,u,\infty)\) ，原理类似

然后就可以跑网络流最小割了

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e5+10,INF=1e9+10;

int n,m,S,T;
char s[N];
struct Edge{
	int to,nxt,w;
}e[N<<1];
int head[N],ecnt=1;
void AddEdge(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}
void Link(int u,int v,int w){ 
	AddEdge(u,v,w),AddEdge(v,u,0);
}

int F[N],X[N],Y[N],col[N],A[N];
// 这里我用带权并查集实现了二分图
int Find(int x){ 
	if(F[x]==x) return x;
	int f=F[x]; F[x]=Find(F[x]);
	col[x]^=col[f];
	return F[x];
}

int dis[N];
int Bfs() {
	rep(i,1,T) dis[i]=INF;
	static queue <int> que;
	dis[S]=0; que.push(S);
	while(!que.empty()) {
		int u=que.front(); que.pop();
		for(int i=head[u];i;i=e[i].nxt) {
			int v=e[i].to,w=e[i].w;
			if(!w || dis[v]<=dis[u]+1) continue;
			dis[v]=dis[u]+1,que.push(v);
		}
	}
	return dis[T]<INF;
}

int Dfs(int u,int in) {
	if(u==T) return in;
	int out=0;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to,w=e[i].w;
		if(!w || dis[v]!=dis[u]+1) continue;
		int t=Dfs(v,min(in-out,w));
		e[i].w-=t,e[i^1].w+=t,out+=t;
		if(in==out) break;
	}
	if(!out) dis[u]=0;
	return out;
}

int Dinic() {
	int ans=0; 
	while(Bfs()) ans+=Dfs(S,INF);
	return ans;
}


int main() {
	rep(kase,1,rd()) {
		n=rd(),m=rd();
		rep(i,1,n) F[i]=i,col[i]=0;
		scanf("%s",s+1);
		S=n+1,T=n+2;
		rep(i,1,n) A[i]=rd();
		rep(i,1,m) {
			X[i]=rd(),Y[i]=rd();
			int x=abs(X[i]),y=abs(Y[i]);
			int u=Find(x),v=Find(y);
			if(u==v) continue;
			F[u]=v,col[u]=col[x]^col[y]^(X[i]<0)^(Y[i]<0)^1;
		}
		rep(i,1,n) Find(i);
		rep(i,1,n) {
			if(col[i]^s[i]^'0') Link(S,i,A[i]);
			else Link(i,T,A[i]);
		}
		rep(i,1,m) {
			int t=col[abs(X[i])]^(X[i]<0);
			assert(col[abs(X[i])]^col[abs(Y[i])]^(X[i]<0)^(Y[i]<0));
			if(t) Link(abs(X[i]),abs(Y[i]),INF);
			else Link(abs(Y[i]),abs(X[i]),INF);
		}
		printf("%d\n",Dinic());
		rep(i,1,T) head[i]=0; ecnt=1;
	}
}