「Solution」最小割测试

Posted on Edited on

…

$\mathbb{Destroy}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

没什么好说的，将点拆成两个，注意输入的顺序。

形式化地，有
$$ V_N = V \cup \{s,t\}\\ E_N = E \cup \{ \mid u \in V\} \cup \{ \mid u' \in V'\}\\ \begin{cases} c(s, u) = w'_u\\ c(v', t) = w_v\\ c(u, v') = \infty\\ \end{cases} $$

$\mathcal{Code}$

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e4 + 100;
const int MAXMAP = 1e2 + 5;
const int INF = 0x3f3f3f3f;

void read(int& x) {
	x = 0; int f = 1;
	char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
	while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	x *= f;
}

int tmp, ans, n, m, st, ed, a[MAXN], b[MAXN], d[MAXN], cur[MAXN];
bool vis_st[MAXN], vis_ed[MAXN], linked[MAXMAP][MAXMAP];
int tot = 1, head[MAXN], nxt[MAXN], edge[MAXN], ver[MAXN];
queue<int> q;

int ind(int x, int k) {
	return x + n * k;
}

void AddEdge(int u, int v, int c) {
 	// printf("%d %d %d\n", u, v, c);
	ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
	ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs(int st) {
	memset(d, 0, sizeof(d));
	while (!q.empty()) q.pop();
	q.push(st), d[st] = 1, cur[st] = head[st];
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = nxt[i]) {
			int v = ver[i];
			if (!edge[i] || d[v] != 0) continue;
			q.push(v); cur[v] = head[v];
			d[v] = d[u] + 1;
			if (v == ed) return true;
		}
	}

	return false;

}

int dinic(int u, int flow) {
	if (u == ed) return flow;
	int res = flow, k, i;
	for (i = cur[u]; i && res; i = nxt[i]) {
		int v = ver[i];
		if (!edge[i] || d[v] != d[u] + 1) continue;
		k = dinic(v, min(res, edge[i]));
		if (k == 0) d[v] = 0;
		edge[i] -= k, edge[i ^ 1] += k;
		res -= k;
		cur[u] = i;
	}
	return flow - res;
}

int main() {

	freopen("destroy.in", "r", stdin);
	freopen("destroy.out", "w", stdout);
	
	read(n), read(m);
	st = 2 * n + 1, ed = 2 * n + 2;

	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i <= n; i++) read(b[i]);

	for (int i = 1, u, v; i <= m; i++) {
		read(u), read(v);

		if (vis_st[u] == 0) AddEdge(st, ind(u, 0), b[u]), vis_st[u] = 1;
		if (linked[ind(u, 0)][ind(v, 1)] == 0) AddEdge(ind(u, 0), ind(v, 1), INF), linked[ind(u, 0)][ind(v, 1)] = 1;
		if (vis_ed[v] == 0) AddEdge(ind(v, 1), ed, a[v]), vis_ed[v] = 1;

	}

	while (bfs(st)) {
		while ((tmp = dinic(st, INF))) ans += tmp;
	}

	printf("%d\n", ans);

	return 0;
}

$\mathbb{Lotus}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

真的吐了，怎么一堆人用$1e6$的点的暴力跑过去。。。
其实和棋盘上的守卫很相似。

对于一个点$(x,y)$，从它可以到达第$x$行，第$y$列的所有其他可行的点。
那么可以将横纵坐标连接，边的容量为$1$表示这两行/列上可行点组成的联通快是可达的。
建一个大源/汇点，分别连向初始/终止点的横纵坐标。边的容量为$+\infty$。

所以最后整张图只有$n + m$个点。

形式化地，设$V$为所有行列编号组成的点集，$P$为可行点的点集，有
$$ P = \{(x,y) \mid map(x,y) = o \} \\ V_N = V \cup \{S,T\}\\ E_N = \{ \mid (u,v) \in P \} \cup \{ \mid (u,v) \in P \} \cup \cup \cup \cup \\ \begin{cases} c(S, s_x) = c(S, s_y) = c(t_x, T) = c(t_y, T) = \infty \\ c(u, v') = c(v', u) = 1 \end{cases} $$

$\mathcal{Code}$

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
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXMAP = 2e2 + 5;
const int MAXN = 4e4 + 500;
const int INF = 0x3f3f3f3f;

void read(int& x) {
	x = 0; int f = 1;
	char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
	while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	x *= f;
}

int n, m, st, ed, ans, tmp, cnt = 2, d[MAXN], cur[MAXN];
char s[MAXMAP][MAXMAP];
bool vis[MAXN];
int tot = 1, head[MAXN], nxt[MAXN], edge[MAXN], ver[MAXN];

queue<int> q;
void AddEdge(int u, int v, int c) {
 	// printf("%d %d %d\n", u, v, c);
	ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
	ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs(int st) {
	memset(d, 0, sizeof(d));
	while (!q.empty()) q.pop();
	q.push(st), d[st] = 1, cur[st] = head[st];
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = nxt[i]) {
			int v = ver[i];
			if (!edge[i] || d[v] != 0) continue;
			q.push(v); cur[v] = head[v];
			d[v] = d[u] + 1;
			if (v == ed) return true;
		}
	}

	return false;

}

int dinic(int u, int flow) {
	if (u == ed) return flow;
	int res = flow, k, i;
	for (i = cur[u]; i && res; i = nxt[i]) {
		int v = ver[i];
		if (!edge[i] || d[v] != d[u] + 1) continue;
		k = dinic(v, min(res, edge[i]));
		if (k == 0) d[v] = 0;
		edge[i] -= k, edge[i ^ 1] += k;
		res -= k;
		cur[u] = i;
	}
	return flow - res;
}

int main() {

	freopen("lotus.in", "r", stdin);
	freopen("lotus.out", "w", stdout);

	read(n), read(m);
	st = n + m + 1, ed = n + m + 2;

	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) if (s[i][j] != '.') {
			AddEdge(i, j + n, 1); AddEdge(j + n, i, 1);
			if (s[i][j] == 'S') AddEdge(st, i, INF), AddEdge(st, j + n, INF);
			if (s[i][j] == 'T') AddEdge(i, ed, INF), AddEdge(j + n, ed, INF);
		}
	}
	
	while (bfs(st)) {
		while ((tmp = dinic(st, INF))) ans += tmp;
	}

	if (ans >= INF) printf("-1\n");
	else printf("%d\n", ans);

	return 0;
}

$\mathbb{Mincut}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

读完题，感觉一脸不可做的样子。。。
然后考试时写了个暴力，乱开数组，直接$\mathtt{MLE \ \ 0}$。。。

首先跑一遍最小割，那么，所有的可行边一定满流了。
再在残余网络上面跑$\mathtt{SCC}$，如果对于一条必须边，它一定分属于两个集合，否则就是一条可行边。

更形式化的，有

$\mathcal{Code}$

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
129
130
131
132
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5e4 + 5;
const int MAXM = 1e5 + 2e4 + 5;
const int INF = 0x3f3f3f3f;

void read(int& x) {
	x = 0; int f = 1;
	char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
	while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	x *= f;
}

int n, m, st, ed, now, ans, tmp, cnt[MAXN], d[MAXM], cur[MAXM];
int tot = 1, head[MAXN], ver[MAXM], edge[MAXM], nxt[MAXM], fr[MAXM], scc;
int dfn[MAXN], low[MAXN], stk[MAXN], vis[MAXN], tp, dn;
bool ex[MAXN];
queue<int> q;

void AddEdge(int u, int v, int c) {
 	// printf("%d %d %d\n", u, v, c);
	ver[++tot] = v, fr[tot] = u, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
	ver[++tot] = u, fr[tot] = v, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs() {
	memset(d, 0, sizeof(d));
	while (!q.empty()) q.pop();
	q.push(st), d[st] = 1, cur[st] = head[st];
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		// printf("%d\n", u);
		for (int i = head[u]; i; i = nxt[i]) {
			int v = ver[i];
			if (!edge[i] || d[v] != 0) continue;
			q.push(v); cur[v] = head[v];
			d[v] = d[u] + 1;
			if (v == ed) return true;
		}
	}

	return false;

}

int dinic(int u, int flow) {
	if (u == ed) return flow;
	int res = flow, k, i;
	for (i = cur[u]; i && res; i = nxt[i]) {
		int v = ver[i];
		if (!edge[i] || d[v] != d[u] + 1) continue;
		now++;
		k = dinic(v, min(res, edge[i]));
		now--;
		if (k == 0) d[v] = 0;
		edge[i] -= k, edge[i ^ 1] += k;
		res -= k;
		cur[u] = i;
	}
	return flow - res;
}

void Tarjan(int u, int fa) {
	dfn[u] = low[u] = ++dn; ex[u] = 1, stk[++tp] = u;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (!edge[i]) continue;
		if (!dfn[v]) {
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if (ex[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		int v; scc++;
		do {
			v = stk[tp--]; vis[v] = scc; ex[v] = 0;
		} while (v != u);
	}
}

int main() {

	freopen("mincut.in", "r", stdin);
	freopen("mincut.out", "w", stdout);
	
	read(n), read(m), read(st), read(ed);

	for (int i = 1, u, v, w; i <= m; i++) read(u), read(v), read(w), AddEdge(u, v, w);

	while (bfs()) {
		// printf("ok\n");
		while ((tmp = dinic(st, INF))) ans += tmp;
	}

	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			Tarjan(i, 0);
		}
	}

	// for (int i = 1; i <= n; i++) {
	// 	printf("%d ", vis[i]);
	// }
	// printf("\n");

	for (int i = 2; i <= tot; i += 2) {

		// printf("%d %d %d\n", fr[i], ver[i], edge[i]);

		if (edge[i] != 0) {
			printf("0 0\n");
		} else {
			if (vis[fr[i]] != vis[ver[i]]) {
				if (vis[ver[i]] == vis[ed] && vis[fr[i]] == vis[st]) {
					printf("1 1\n");
				} else {
					printf("1 0\n");
				}
			} else printf("0 0\n");
		}
	}

	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」