【题解】CF311E Biologist

Posted on Edited on

简要题意

有一个长度为 $n$ 的 $01$ 串, 将第 $i$ 个位置变为另外一个数字的代价是 $v_i$ .

有 $m$ 个要求, 每个要求的形式是给定 $k_i$ 个位置, 这些位置都需要是 $0$ 或 $1$ , 若这些位置都满足要求则可获得 $W_i$ 元, 某些要求如果未达成还要倒贴 $g$ 元.

问最大利润.

$n \leqslant 10^4,m \leqslant 2\times 10^3,k_i \leqslant 10$ .

题解

又变成 $0$ 又变成 $1$ 很麻烦, 我们考虑先全变成 $1$ 的答案, 为所有要求为 $1$ 的 $W_i$ 之和, 减去所有 $0$ 点的修改代价, 再减去 $g$ 乘上 $0$ 要求中要求倒贴的个数.

现在, 我们再来考虑满足一个 $0$ 的要求, 这样所有相关的点都需要修改, 而且修改与贡献变化之间相互有牵制关系, 如果一个点进行了修改那么有关该点的所有 $1$ 的要求也得修改.

这个性质符合最大闭合子图,考虑建图.

考虑原先为 $0$ 的点, 因为之前被修改过一次, 再次修改相当于反悔, 会产生 $v_i$ 的贡献.

原先为 $1$ 的点则是 $-v_i$ 的贡献.

对于每个 $0$ 的要求, 如果将该要求改为满足, 会产生 $W_i$ 的贡献, 如果有要求倒贴, 则会产生 $W_i+g$ 的贡献. 将贡献作为点的权值, 所有与它相关的点 $(\text{即被要求的点})$ 都必须选择, 于是该要求向所有有关的点连有向边.

对于每个 $1$ 的要求, 如果改为不满足, 会产生 $-W_i$ 的贡献, 如果要求倒贴, 则会产生 $-W_i-g$ 的贡献.与它相关的点有一个不满足则它也不满足, 于是所有与它相关的点向该要求连有向边.

之前的答案加上最大权闭合子图即为答案.

发现会有抵消, 则最后答案就是 $\sum{W_i}-\text{最小割}$ .

代码

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
118
119
120
121
122
123
124
125
126
127
128
/************************************************
*Author        :  demonlover
*Created Time  :  2021.11.10.00:41
*Problem       :  CF311E
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
	int f = 1,c = getchar();x = 0;
	while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
	while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
	return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
	return read(x) && read(args...);
}

namespace run {
	const int maxn = 3e5+10,maxm = 3e5+10;
	const int inf = 1<<30;
	struct Edge {int nxt,to,w;}edge[maxm<<1];
	int begn[maxn],e = 1,cur[maxn];
	int dep[maxn];
	bool vis[maxn];
	int a[maxn],v[maxn];
	int ans,n,m,g,s,t;
	queue<int> q;
	inline void add(int x,int y,int z) {
		edge[++e] = (Edge){begn[x],y,z};begn[x] = e;
		return;
	}
	inline void addedge(int x,int y,int z) {
		add(x,y,z);add(y,x,0);
		return;
	}
	inline bool bfs() {
		for (register int i = 0;i <= n+m+1;++i)dep[i] = 0x3f3f3f3f,cur[i] = begn[i],vis[i] = false;
		dep[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			vis[x] = false;
			for (register int i = begn[x];i;i = edge[i].nxt) {
				int y = edge[i].to;
				if (dep[y] > dep[x]+1 && edge[i].w) {
					dep[y] = dep[x]+1;
					if (!vis[y])q.push(y),vis[y] = true;
				}
			}
		}
		return dep[t] != 0x3f3f3f3f;
	}
	bool Flag;
	inline int dfs(int x,int flow,int &res) {
		int tflow = 0;
		if (x == t) {
			Flag = true;
			res += flow;
			return flow;
		}
		int used = 0;
		for (register int i = cur[x];i;i = edge[i].nxt) {
			cur[x] = i;
			int y = edge[i].to;
			if (dep[y] == dep[x]+1 && edge[i].w)
				if (tflow = dfs(y,min(edge[i].w,flow-used),res)) {
					used += tflow;
					edge[i].w -= tflow;
					edge[i^1].w += tflow;
					if (used == flow)break;
				}
		}
		return used;
	}
	inline int Dinic() {
		int res = 0,low;
		while (bfs()) {
			Flag = true;
			while (Flag)Flag = false,dfs(s,inf,res);
		}
		return res;
	}
	inline int main() {
		read(n,m,g);s = 0;t = n+m+1;
		for (register int i = 1;i <= n;++i)read(a[i]);
		for (register int i = 1;i <= n;++i)read(v[i]);
		for (register int i = 1;i <= n;++i) {
			if (!a[i])addedge(s,i,v[i]);
			else addedge(i,t,v[i]);
		}
		for (register int i = 1;i <= m;++i) {
			int b,w,k,p;
			read(b,w);
			ans += w;
			read(k);
			for (register int j = 1,x;j <= k;++j) {
				read(x);
				if (!b)addedge(n+i,x,inf);
				else addedge(x,n+i,inf);
			}
			read(p);
			if (p)w += g;
			if (!b)addedge(s,n+i,w);
			else addedge(n+i,t,w);
		}
		printf("%d\n",ans-Dinic());
		cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
		return 0;
	}
}

#define demonlover
int main() {
#ifdef demonlover
	freopen("CF311E.in","r",stdin);
	freopen("CF311E.out","w",stdout);
#endif
	return run :: main();
}