水题记录(七)

题目名称 文本生成器 文理分科 Kos-Dicing 最小生成树 Exca王者之剑
标签 AC自动机,动态规划 网络流 网络流 网络流 网络流
来源 BZOJ 1030 BZOJ 3894 BZOJ 1532 BZOJ 2561 BZOJ 1324

BZOJ 1030

题意:

给定 $n$ 个模式串, 求长度为 $m$ 且包含上述任意一个模式串的字符串的个数

题解:

神题啊,AC自动机上的动态规划,状态 $dp[i][j]$ 表示前 $i$ 确定了个字符且在AC自动机上匹配到了第 $j$ 个位置的方案数,如果发现已经包含了一个模式串,那么后面的字符随便取,用快速幂即可。

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int mod = 10007;
const int maxn = 6e3 + 10;;
int c[maxn][26], f[maxn], dp[maxn][maxn], tot;
ll ans;
bool v[maxn];
void insert(char *s) {
int len = strlen(s), now = 0;
for (int i = 0; i < len; i++) {
if (!c[now][s[i] - 'A'])
c[now][s[i] - 'A'] = ++tot;
now = c[now][s[i] - 'A'];
}
v[now] = true;
}
void build() {
std::queue<int>q;
for (int i = 0; i < 26; i++)
if (c[0][i])
f[c[0][i]] = 0, q.push(c[0][i]);
while (q.size()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i++)
if (c[u][i]) f[c[u][i]] = c[f[u]][i], q.push(c[u][i]);
else c[u][i] = c[f[u]][i];
}
}
int ksm(int x, int y) {
int z = 1;
while (y) {
if (y & 1) z = x * z % mod;
y >>= 1; x = x * x % mod;
}
return z;
}
char s[maxn];
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s); insert(s);
}
build();
dp[0][0] = 1;
for (int i = 1; i <= tot; i++)
for (int j = i; j; j = f[j]) v[i] |= v[j];
for (int i = 1; i <= m; i++) {
for (int now = 0; now <= tot; now++) {
for (int ch = 0; ch < 26; ch++) {
int nxt = c[now][ch];
(dp[i][nxt] += dp[i - 1][now]) %= mod;
}
}
for (int nxt = 0; nxt <= tot; nxt++)
if (v[nxt]) ans = (ans + ksm(26, m - i) * dp[i][nxt] % mod) % mod, dp[i][nxt] = 0;
}
printf("%lld\n", ans);
}
/*
5 14
ASCASSF
ADGFGH
SFGSDFG
SDGSDFH
SDFSDRT
*/

BZOJ 3894

题意:

文理分科是一件很纠结的事情!(虽然看到这个题目的人肯定都没有纠
结过)
小P所在的班级要进行文理分科。他的班级可以用一个$n×m$的矩阵进行
描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到:
1.如果第$i$行第$j$列的同学选择了文科,则他将获得$art[i][j]$的满意值,如
果选择理科,将得到$science[i][j]$的满意值。
2.如果第$i$行第$j$列的同学选择了文科,并且他相邻(两个格子相邻当且
仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开
心,所以会增加$same_art[i][j]$的满意值。
3.如果第i行第j列的同学选择了理科,并且他相邻的同学全部选择了理
科,则增加 $same_science[i][j]$的满意值。
小P想知道,大家应该如何选择,才能使所有人的满意值之和最大。请
告诉他这个最大值。

题解:

转自$Heret1c$
初看是一个中规中矩的网络流裸题,先摆上源点$S$汇点$T$,对于点$P$,直接连上$S-(A[p])->P$和$P-(B[p])->T$,这便是不考虑其他附加的条件时的建图方式,要用此图求得最终答案,只需要求出最小割(即那些放弃的选择),然后用总价值减去即可。
现在来看看另外两个条件,不妨以理科为例,这两个可以被翻译成——如果$P$及$P$周围的四个点都选择理科,那么就加上额外的$D[P]$的价值,进一步被翻译为——如果割边都是文科,那么就不用割掉价值为$D[P]$的这条边(虽然目前我们还不知道这条边是怎么放的),它的反面便是——如果这几个点有文科边(假定是与$S$相连的边)没有被割掉,那么此时必须还要割掉一条价值为$D[P]$的边,才能使得源点$S$和汇点$T$不连通。
那么,这条价值为$C[P]$的边在哪里?答案便在下图。

像这样虚拟出来一个额外的点,那么只要和当前$X$相连的点与$S$相连的边没有被割掉,就一定会割掉$X-(D[P])->T$这条边,即可达成这一目的——若有任意一个条件达成(或者没有达成),就必须舍弃一部分价值。这便是多对一的限制,可以建一个中间源点(汇点)来解决。

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 <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define nl NULL
using namespace std;
const int inf = 1e9;
const int maxn = 1001000;
struct Graph {
struct edge {
int to, cap, nxt;
edge(int x = 0, int y = 0, int w = 0) {
to = x; cap = y; nxt = w;
}
}e[maxn << 1];
int p[maxn], cnt, s, t, dep[maxn];
Graph() {
cnt = 1;
}
void add(int x, int y, int w) {
e[++cnt] = edge(y, w, p[x]); p[x] = cnt;
e[++cnt] = edge(x, 0, p[y]); p[y] = cnt;
}
bool bfs() {
queue<int>q;
memset(dep, -1, sizeof(dep));
q.push(s); dep[s] = 0;
while(q.size()) {
int u = q.front(); q.pop();
for(int i = p[u]; i; i = e[i].nxt) if(e[i].cap){
int v = e[i].to;
if(dep[v] == -1) {
dep[v] = dep[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u, int c) {
if(u == t || !c) return c;
int f = 0;
for(int i = p[u]; i; i = e[i].nxt) if(e[i].cap && dep[u] + 1 == dep[e[i].to]){
int a = dfs(e[i].to, min(c, e[i].cap));
e[i].cap -= a; e[i ^ 1].cap += a;
f += a; c -= a;
if(!c) break;
}
if(!f) dep[u] = -1; return f;
}
int dinic(int S, int T) {
s = S; t = T;
int flow = 0;
while(bfs())
flow += dfs(s, inf);
return flow;
}
}g;
inline int read(){
int u = 0; char c = getchar();
for (;!isdigit(c); c = getchar());
for (; isdigit(c); c = getchar()) u = u * 10 + c - 48;
return u;
}
int A[101][101], B[101][101], C[101][101], D[101][101];
#define id(x, y) ((x - 1) * m + y)
int dx[]{0, 0, 1, -1, 0}, dy[]{1, -1, 0, 0, 0};
int main(){
int n = read(), m = read(), ans = 0, cnt = id(n, m);
int S = ++cnt, T = ++cnt;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += (A[i][j] = read());
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += (B[i][j] = read());
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += (C[i][j] = read());
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += (D[i][j] = read());
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
g.add(S, id(i, j), A[i][j]);
g.add(id(i, j), T, B[i][j]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int tmp = ++cnt;
for (int k = 0; k <= 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || y < 1 || x > n || y > m) continue;
//g.add(id(x, y), tmp, inf);
g.add(tmp, id(x, y), inf);
}
g.add(S, tmp, C[i][j]);
//g.add(tmp, T, D[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int tmp = ++cnt;
for (int k = 0; k <= 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || y < 1 || x > n || y > m) continue;
g.add(id(x, y), tmp, inf);
//g.add(tmp, id(x, y), inf);
}
//g.add(S, tmp, C[i][j]);
g.add(tmp, T, D[i][j]);
}
}
printf("%d\n", ans - g.dinic(S, T));
return 0;
}

BZOJ 1532

题意:

Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.

题解:

二分 + 网络流,当时傻傻的去打二分 + 贪心了,然后发现自己都能$hack$自己,最后在$Heret1c$的提示下算是独立想出来的建图的方法吧,想必还是我太菜了$QAQ$

顺便说一句,$dfs$函数里面那个$if(!r) dep[u] = 0$这句话非常重要,$TLE$与$Rank1$的差距

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
#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define nl NULL
using namespace std;
inline int read() {
int u = 0, f = 1; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = 0;
for (; isdigit(c); c = getchar()) u = u * 10 + c - 48;
return f ? u : -u;
}
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int inf = 1e9;
int n, m;
pair<int, int>eg[maxm];
#define S (n + m + 1)
#define T (n + m + 2)
namespace MaxFlow {
struct edge {
int to, nxt, cap;
edge(int x = 0, int y = 0, int z = 0) {
to = x; nxt = y; cap = z;
}
}e[maxm << 1]; int head[maxn << 1], cnt = 1;
int dep[maxn << 1];
void add(int x, int y, int w) {
e[++cnt] = edge(y, head[x], w); head[x] = cnt;
e[++cnt] = edge(x, head[y], 0); head[y] = cnt;
}
void build(int ans) {
cnt = 1;
memset(head, 0, sizeof(int) * (n + m + 5));
for (int i = 1; i <= m; i++) {
add(S, i, 1);
add(i, eg[i].first + m, 1);
add(i, eg[i].second + m, 1);
}
for (int i = 1; i <= n; i++) add(i + m, T, ans);
}
bool bfs(int s, int t) {
queue<int>q; q.push(s);
//memset(dep, 0, sizeof(int) * (n + m + 5));
memset(dep, 0, sizeof(dep));
dep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v]) continue;
dep[v] = dep[u] + 1;
if (!dep[t])q.push(v);
}
}
return dep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v] != dep[u] + 1) continue;
int a = dfs(v, t, min(f, e[i].cap));
f -= a; e[i].cap -= a; e[i ^ 1].cap += a; r += a;
}
if (!r) dep[u] = 0;
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
}
bool check(int ans) {
MaxFlow::build(ans);
return MaxFlow::dinic(S, T) == m;
}
int main() {
n = read(); m = read();
for (int i = 1; i <= m; i++)
eg[i].first = read(), eg[i].second = read();
int l = 1, r = m;
while (l < r) {
int mid = (l + r >> 1);
if (check(mid)) r = mid;
else l = mid + 1;
}
return 0 * printf("%d", l);
}
/*
6 10
1 2
2 1
1 3
3 1
2 3
3 2
1 2
1 2
2 3
2 3
*/

BZOJ 2561

题意:

 给定一个边带正权的连通无向图G=(V,E),其中N=|V|,M=|E|,N个点从1到N依次编号,给定三个正整数u,v,和L (u≠v),假设现在加入一条边权为L的边(u,v),那么需要删掉最少多少条边,才能够使得这条边既可能出现在最小生成树上,也可能出现在最大生成树上?

题解:

  • 错误的建图方法

考虑到在生成树中,如果必须要选$u<-(L)->v$这条边,即在选择这条边之前,$u$和$v$不能连通,在最小生成树和最大生成树中,与此边权相等的边我们肯定不选,那么就相当于在剩下的边集里面求出使得$u$到$v$不连通的最小割即可,所以我是这么建图的:

建出网络流的双向边,即正向边和反向边容量相同,如果边权和$L$相同,就连容量为$0$的边,不然,就连容量为$1$的边,跑$u$到$v$的最大流即可

1
2
for (int i = 1; i <= m; i++)
MaxFlow::add(a[i], b[i], c[i] == w ? 0 : 1);

然而这么做有一个问题,不妨看以下样例

1
2
3
4
3 2
1 3 1
2 3 100
1 2 10

在这个样例中,图是这么样的(意会一下)
$[1]<-(1)->[3]<-(100)->[2]$
显然如果按这个图求最小割,使得$[1]$,$[2]$不连通,那么最少割去一条边,然而这个图并不需要割去任何一条边即可保证最小生成树和最大生成树里面都包含边$[1]<-(10)->[2]$,大家此时因该也想明白了吧

  • 正确的建图方法

将最大生成树所需的割边与最小生成树所需的割边分开来求,上面的例子也说明了,一起求会有问题,因为所求的东西和题目的要求不等价,所以正确的建图方式应该是这样的

建两次图,第一次计算最小生成树时需要删除的边,即边权小于$L$的,记为$ans1$;第二次计算最小生成树时需要删除的边,即边权大于$L$的,记为$ans2$。那么最终答案便是$ans1 + ans2$

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= m; i++)
if (c[i] < w)
MaxFlow::add(a[i], b[i], 1);
ans1 = MaxFlow::dinic(s, t);
MaxFlow::clear(n);
for (int i = 1; i <= m; i++)
if (c[i] > w)
MaxFlow::add(a[i], b[i], 1);
ans2 = MaxFlow::dinic(s, t);

我们来看看哪里不等价。在求取最小生成树时,不小于$L$的边不会有贡献,在求取最大生成树时,不大于$L$的边不会有贡献,那么在错误的建图中,两种本不会有交集的边集共同作用下,就使得我们在考虑最小生成树时还得顾虑到如果此时求最大生成树那条边会不会被包括进来的问题,然而这两个问题并不应该一起考虑,显然,影响最小生成树的边集不会与影响最大生成树的边集有交集,这也是为什么我们可以分开求,且分开求是正确的方法的原因

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
#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define nl NULL
using namespace std;
inline int read() {
int u = 0, f = 1; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = 0;
for (; isdigit(c); c = getchar()) u = u * 10 + c - 48;
return f ? u : -u;
}
const int maxn = 2e4 + 10;
const int maxm = 2e5 + 10;
const int inf = 1e9;
namespace MaxFlow {
struct edge {
int to, nxt, cap;
edge(int x = 0, int y = 0, int z = 0) {
to = x; nxt = y; cap = z;
}
}e[maxm << 1]; int head[maxn], cnt = 1;
int dep[maxn];
void add(int x, int y, int w) {
e[++cnt] = edge(y, head[x], w); head[x] = cnt;
e[++cnt] = edge(x, head[y], w); head[y] = cnt;
}
/*
void build(int ans) {
cnt = 1;
memset(head, 0, sizeof(int) * (n + m + 5));
for (int i = 1; i <= m; i++) {
add(S, i, 1);
add(i, eg[i].first + m, 1);
add(i, eg[i].second + m, 1);
}
for (int i = 1; i <= n; i++) add(i + m, T, ans);
}
*/
bool bfs(int s, int t) {
queue<int>q; q.push(s);
//memset(dep, 0, sizeof(int) * (n + m + 5));
memset(dep, 0, sizeof(dep));
dep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v]) continue;
dep[v] = dep[u] + 1;
if (!dep[t])q.push(v);
}
}
return dep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v] != dep[u] + 1) continue;
int a = dfs(v, t, min(f, e[i].cap));
f -= a; e[i].cap -= a; e[i ^ 1].cap += a; r += a;
}
if (!r) dep[u] = 0; return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
void clear(int n) {
cnt = 1;
memset(head, 0, sizeof(head));
}
}
int a[maxm], b[maxm], c[maxm], ans1, ans2;
int main() {
int n = read(), m = read();
for (int i = 1; i <= m; i++)
a[i] = read(), b[i] = read(), c[i] = read();
int s = read(), t = read(), w = read();
for (int i = 1; i <= m; i++)
if (c[i] < w)
MaxFlow::add(a[i], b[i], 1);
ans1 = MaxFlow::dinic(s, t);
MaxFlow::clear(n);
for (int i = 1; i <= m; i++)
if (c[i] > w)
MaxFlow::add(a[i], b[i], 1);
ans2 = MaxFlow::dinic(s, t);
printf("%d", ans1 + ans2);
}
/*
8 12
4 7 2
3 5 6
2 5 1
1 2 10
1 3 10
1 4 10
6 2 8
3 7 5
5 4 3
5 8 10
6 8 10
7 8 10
1 8 5
*/

BZOJ 1324

题意


题解

不难发现,相邻的宝石是不可能的同时选择的,所以将网格黑白染色,黑格连源点,白格连汇点,边权即为点权,然后黑格再向相邻的白格连边权正无穷的边即可,这样即可表示,对于相邻的格子,必定要割掉其中至少一个才能使得源点和汇点不连通,正好符合题意。

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 <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define nl NULL
using namespace std;
inline int read() {
int u = 0, f = 1; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = 0;
for (; isdigit(c); c = getchar()) u = u * 10 + c - 48;
return f ? u : -u;
}
const int maxn = 1e4 + 10;
const int maxm = 2e5 + 10;
const int inf = 1e9;
namespace MaxFlow {
struct edge {
int to, nxt, cap;
edge(int x = 0, int y = 0, int z = 0) {
to = x; nxt = y; cap = z;
}
}e[maxm << 1]; int head[maxn], cnt = 1;
int dep[maxn];
void add(int x, int y, int w) {
e[++cnt] = edge(y, head[x], w); head[x] = cnt;
e[++cnt] = edge(x, head[y], 0); head[y] = cnt;
}
bool bfs(int s, int t) {
queue<int>q; q.push(s);
memset(dep, 0, sizeof(dep));
dep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v]) continue;
dep[v] = dep[u] + 1;
if (!dep[t])q.push(v);
}
}
return dep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v] != dep[u] + 1) continue;
int a = dfs(v, t, min(f, e[i].cap));
f -= a; e[i].cap -= a; e[i ^ 1].cap += a; r += a;
}
if (!r) dep[u] = 0; return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
}
#define id(i, j) ((i - 1) * m + j)
int n, m;
bool in_map(int x, int y) {
return x > 0 && y > 0 && x <= n && y <= m;
}
int dx[]{0, 0, 1, -1}, dy[]{1, -1, 0, 0};
int main() {
n = read(), m = read();
int ans = 0, s = n * m + 1, t = n * m + 2, now;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
ans += (now = read());
if ((i ^ j) & 1) MaxFlow::add(s, id(i, j), now);
else {MaxFlow::add(id(i, j), t, now); continue;}
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (in_map(x, y))
MaxFlow::add(id(i, j), id(x, y), inf);
}
}
printf("%d\n", ans - MaxFlow::dinic(s, t));
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :