关键边

Acwing2236
Acwing2236

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
const int maxn = 510, maxm = (maxn + 5000) * 2;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int n, m, S, T;
void add(int a, int b, int c) {
ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int d[maxn], cur[maxn];
bool bfs() {
memset(d, -1, sizeof d);
queue<int> q;
d[S] = 0, cur[S] = head[S];
q.push(S);

while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (d[y] == -1 && e[i]) {
d[y] = d[x] + 1;
cur[y] = head[y];
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

int dinic(int u, int lim) {
if (u == T) return lim;
int flow = 0;
for (int i = cur[u]; i && lim > flow; i = ne[i]) {
cur[u] = i;
int v = ver[i];
if (d[v] == d[u] + 1 && e[i]) {
int t = dinic(v, min(e[i], lim - flow));
if (!t) d[v] = -1;
flow += t, e[i] -= t, e[i^1] += t;
}
}
return flow;
}

int dinic() {
int res = 0, flow;
while (bfs()) while (flow = dinic(S, inf)) res += flow;
return res;
}

bool vis_s[maxn], vis_t[maxn];
void dfs(int u, bool st[], int fl) {
st[u] = true;
for (int i = head[u]; i; i = ne[i]) {
int j = i ^ fl, v = ver[i];
if (!st[v] && e[j]) dfs(v, st, fl);
}
}

void solve() {
int res = 0;
for (int i = 2; i < 2 + m*2; i += 2) {
if (!e[i] && vis_s[ ver[i^1] ] && vis_t[ ver[i] ]) res++;
}
printf("%d\n", res);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
S = 0, T = n-1;
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}

dinic();
dfs(S, vis_s, 0);
dfs(T, vis_t, 1);

solve();
}

二分与最大流

Acwing2277
Acwing2277

特殊情况
如果是无向图,要求每条边最多只能走一次,在建流网络的时候
(u,v)(u, v) 正向走一次,(v,u)(v, u) 反向又走了一次,等价于没有流
把相应的边删去即可

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
const int maxn = 200 + 10, maxm = (maxn + 40000) * 2;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], w[maxm], ne[maxm], idx = 1;
int n, m, S, T, K;

void add(int a, int b, int c) {
ver[++idx] = b; w[idx] = c; ne[idx] = head[a]; head[a] = idx;
ver[++idx] = a; w[idx] = c; ne[idx] = head[b]; head[b] = idx;
}

int d[maxn], cur[maxn];
bool bfs() {
memset(d, -1, sizeof d);
d[S] = 0, cur[S] = head[S];
queue<int> q; q.push(S);

while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (d[y] == -1 && e[i]) {
d[y] = d[x] + 1;
cur[y] = head[y];
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

int dinic(int u, int lim) {
if (u == T) return lim;
int flow = 0;
for (int i = cur[u]; i && lim > flow; i = ne[i]) {
cur[u] = i;
int v = ver[i];
if (d[v] == d[u] + 1 && e[i]) {
int t = dinic(v, min(e[i], lim-flow));
if (!t) d[v] = -1;
flow += t, e[i] -= t, e[i^1] += t;
}
}
return flow;
}

int dinic() {
int res = 0, flow;
while (bfs()) while (flow = dinic(S, inf)) res += flow;
return res;
}

bool check(int x) {
for (int i = 2; i <= idx; i++) {
if (w[i] > x) e[i] = 0;
else e[i] = 1;
}
return dinic() >= K;
}

void solve() {
int l = 1, r = 1e6;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d", &n, &m, &K);
S = 1, T = n;
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}

// then solve
solve();
}

分层图和最大流判定

dinicgraph
Acwing2187
Acwing2187-01
Acwing2187-02

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
const int maxn = 22*1100 + 10, maxm = (maxn + 1100 + 22*1100) * 2 + 10;
const int inf = 0x3f3f3f3f;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int n, m, K, S, T;
void add(int a, int b, int c) {
ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int pa[maxn];
int found(int x) {
return x == pa[x] ? x : pa[x] = found(pa[x]);
}

class Ship {
public:
int H, r, s[16];
} ships[30];

inline int get(int day, int i) {
return day * (n+2) + i;
}

int d[maxn], cur[maxn];
bool bfs() {
memset(d, -1, sizeof d);
d[S] = 0, cur[S] = head[S];
queue<int> q; q.push(S);

while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (d[y] == -1 && e[i]) {
d[y] = d[x] + 1;
cur[y] = head[y];
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

int dinic(int u, int lim) {
if (u == T) return lim;
int flow = 0;
for (int i = cur[u]; i && lim > flow; i = ne[i]) {
cur[u] = i;
int v = ver[i];
if (d[v] == d[u] + 1 && e[i]) {
int t = dinic(v, min(e[i], lim - flow));
if (!t) d[v] = -1;
flow += t, e[i] -= t, e[i^1] += t;
}
}
return flow;
}

int dinic() {
int res = 0, flow;
while (bfs()) while (flow = dinic(S, inf)) res += flow;
return res;
}

void solve() {
add(S, get(0, 0), K);
add(get(0, n+1), T, inf);

int day = 1, res = 0;
while (true) {
add(get(day, n+1), T, inf);
for (int i = 0; i <= n+1; i++) {
add(get(day-1, i), get(day, i), inf);
}

for (int i = 0; i < m; i++) {
int r = ships[i].r;
int s1 = ships[i].s[ (day-1) % r ], s2 = ships[i].s[ day % r ];
add(get(day-1, s1), get(day, s2), ships[i].H);
}

res += dinic();
if (res >= K) break;
day++;
}
printf("%d\n", day);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d", &n, &m, &K);
for (int i = 0; i <= 30; i++) pa[i] = i;
S = maxn - 2, T = maxn - 1;
for (int i = 0; i < m; i++) {
scanf("%d%d", &ships[i].H, &ships[i].r);
int b = ships[i].r;
for (int j = 0; j < b; j++) {
scanf("%d", &ships[i].s[j]);
if (ships[i].s[j] == -1) ships[i].s[j] = n+1;
if (j) pa[found(ships[i].s[j-1])] = found(ships[i].s[j]);
}
}

if (found(0) != found(n+1)) {
puts("0");
return 0;
}

// then solve
solve();
}

分层图最大流方案输出

codeforces101388B

  • ii 个星球,第dayday 天的状态节点是get(day,i)\textbf{get}(day, i)
  • 为了便于输出,mm 条双向隧道可以用二元组edges(u,v)\text{edges}(u, v) 预先存起来

    c(get(day1,u), get(day,v))=1c(get(day1,v), get(day,u))=1\begin{gathered} c\left( \text{get}(day-1, u), \ \text{get}(day, v) \right) = 1 \\ c\left( \text{get}(day-1, v), \ \text{get}(day, u) \right) = 1 \end{gathered}

    用一个map: PIIint\textbf{map:} \ \text{PII} \to \text{int} 分别记录这两条边的编号,当然,只需要记录正向边

    map{(day1,u),(day,v)}=idx1map{(day1,v),(day,u)}=idx2\begin{gathered} \text{map}\{ (day-1, u), (day, v) \} = \text{idx}_1 \\ \text{map}\{ (day-1, v), (day, u) \} = \text{idx}_2 \end{gathered}

这里我们用EE 表示流网络中的容量边,用ee 表示隧道边

  • 输出的时候从第00 天到第dayday 天依次输出,需要记录一下i[1K]i \in [1\cdots K] 每个飞行器位置location[i]\text{location}[i]
    初始化location[1K]=s\text{location}[1\cdots K] = s(在起点处),假设当前是第pp 天:
    • for p[0day]\textbf{for} \ \forall p \in [0\cdots day],对于第pp 天,初始化这一天的决策集合sol[]\textbf{sol}[\cdots]
      for i[0,m)\textbf{for} \ \forall i \in [0, m) 依次检查每一条隧道,对于隧道e(i):(u,v)\text{e}(i):(u, v)
      f1|f1| 表示(p1,u)(p,v)(p-1, u) \to (p, v) 的流量,用f2|f2| 表示(p1,v)(p,u)(p-1, v) \to (p, u) 的流量

      f1=E(map{(p1,u),(p,v)}1)f2=E(map{(p1,v),(p,u)}1)\begin{gathered} |f1| = E\left(\quad \text{map}\{ (p-1, u), (p, v) \} \oplus 1 \quad \right) \\ |f2| = E\left(\quad \text{map}\{ (p-1, v), (p, u) \} \oplus 1 \quad \right) \end{gathered}

      {f1=1 and f2=0(u,v)加入决策集 solf2=1 and f1=0(v,u)加入决策集 sol\begin{cases} |f1| = 1 \ \textbf{and} \ |f2| = 0 && (u, v) \text{加入决策集 sol} \\ |f2| = 1 \ \textbf{and} \ |f1| = 0 && (v, u) \text{加入决策集 sol} \end{cases}

    • 初始化数组moved[1K]=0\text{moved}[1 \cdots K] = 0,表示这一天没有飞机起飞
      for isol[]\textbf{for} \ \forall i \in \text{sol}[\cdots] ,遍历决策集,对于sol[i]:(u,v)\textbf{sol}[i]: (u, v),遍历每架飞机
      for j[1K]\quad \textbf{for} \ \forall j \in [1\cdots K]if location[j]=u and moved(j)=0\textbf{if} \ \text{location}[j] = u \ \textbf{and} \ \text{moved}(j) = 0
      location[j]v,moved[j]1,print(j,v)\quad \quad \text{location}[j] \leftarrow v, \quad \text{moved}[j] \leftarrow 1, \quad \text{print}(j, v)
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
133
134
135
136
137
typedef pair<int, int> PII;
const int maxn = 50010, maxm = (maxn + 1000 + 200*1000)*2 + 10;
const int inf = 0x3f3f3f3f;
int n, m, K, s, t, S, T;
vector<PII> tunnel;
map<PII, int> mp;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
void add(int a, int b, int c) {
ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

inline int get(int day, int i) {
return day*(n+1) + i;
}

int d[maxn], cur[maxn];
bool bfs() {
memset(d, -1, sizeof d);
d[S] = 0, cur[S] = head[S];
queue<int> q; q.push(S);

while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (d[y] == -1 && e[i]) {
d[y] = d[x] + 1;
cur[y] = head[y];
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

int dinic(int u, int lim) {
if (u == T) return lim;
int flow = 0;
for (int i = cur[u]; i && lim > flow; i = ne[i]) {
cur[u] = i;
int v = ver[i];
if (d[v] == d[u] + 1 && e[i]) {
int t = dinic(v, min(e[i], lim-flow));
if (!t) d[v] = -1;
flow += t, e[i] -= t, e[i^1] += t;
}
}
return flow;
}

int dinic() {
int res = 0, flow;
while (bfs()) while (flow = dinic(S, inf)) res += flow;
return res;
}

int day = 1;
void solve() {
add(S, get(0, s), K);
add(get(0, t), T, inf);
day = 1;
int res = 0;
while (true) {
add(get(day, t), T, inf);
for (int i = 1; i <= n; i++) add(get(day-1, i), get(day, i), inf);
for (auto x : tunnel) {
int u = x.first, v = x.second;
add(get(day-1, u), get(day, v), 1);
mp[ {get(day-1, u), get(day, v)} ] = idx - 1;

add(get(day-1, v), get(day, u), 1);
mp[ {get(day-1, v), get(day, u)} ] = idx - 1;
}

res += dinic();
if (res >= K) break;
day++;
}
printf("%d\n", day);
}

void out() {
vector<int> location(K, s);
for (int p = 1; p <= day; p++) {
vector<PII> sol;
vector<int> moved(K, 0);

for (auto x : tunnel) {
int u = x.first, v = x.second;
int id1 = mp[ {get(p-1, u), get(p, v)} ];
int id2 = mp[ {get(p-1, v), get(p, u)} ];

int f1 = e[id1 ^ 1], f2 = e[id2 ^ 1];
if (f1 == 1 && f2 == 0) sol.push_back( {u, v} );
if (f1 == 0 && f2 == 1) sol.push_back( {v, u} );
}

printf("%d", (int)sol.size());

vector<PII> ans;
for (auto x : sol) {
int u = x.first, v = x.second;
for (int i = 0; i < K; i++) {
if (!moved[i] && location[i] == u) {
ans.push_back( {i+1, v} );
moved[i] = true;
location[i] = v;
break;
}
}
}
sort(ans.begin(), ans.end());
for (auto x : ans) printf(" %d %d", x.first, x.second);
printf("\n");
}
}

int main() {
freopen("bring.in", "r", stdin);
freopen("bring.out", "w", stdout);
scanf("%d%d%d%d%d", &n, &m, &K, &s, &t);
S = maxn-1, T = maxn-2;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
tunnel.push_back({u, v});
}

// solve
solve();

// out
out();
}

匹配与拆点

Acwing2240
Acwing2240-01
Acwing2240-02

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
const int maxn = 400 + 10, maxm = (maxn + 410000) * 2;
const int inf = 0x3f3f3f3f;
int n, F, D, S, T;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
void add(int a, int b, int c) {
ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int d[maxn], cur[maxn];
bool bfs() {
memset(d, -1, sizeof d);
d[S] = 0, cur[S] = head[S];
queue<int> q; q.push(S);

while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (d[y] == -1 && e[i]) {
d[y] = d[x] + 1;
cur[y] = head[y];
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

int dinic(int u, int lim) {
if (u == T) return lim;
int flow = 0;
for (int i = cur[u]; i && lim > flow; i = ne[i]) {
cur[u] = i;
int v = ver[i];
if (d[v] == d[u] + 1 && e[i]) {
int t = dinic(v, min(e[i], lim - flow));
if (!t) d[v] = -1;
flow += t, e[i] -= t, e[i^1] += t;
}
}
return flow;
}

int dinic() {
int res = 0, flow;
while (bfs()) while (flow = dinic(S, inf)) res += flow;
return res;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d", &n, &F, &D);
S = 0, T = 2*n + F + D + 2;

// prework
for (int i = 1; i <= F; i++) add(S, 2*n + i, 1);
for (int i = 1; i <= D; i++) add(2*n + F + i, T, 1);
for (int i = 1; i <= n; i++) add(i, n+i, 1);

// get data
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
while (a--) {
int t;
scanf("%d", &t);
add(2*n + t, i, 1);
}
while (b--) {
int t;
scanf("%d", &t);
add(n+i, 2*n + F + t, 1);
}
}

int ans = dinic();
printf("%d\n", ans);
}