先来回顾一下dinic\textbf{dinic} 算法执行多路增广的过程
f|f| 是最大可行流的条件是,当且仅当GfG_fSTS \rightsquigarrow T 一条增广路径都没有
augment

拆点

takeapart

有向图的不相交路径

最大流可以解决的一种重要的模型,可以简单描述为
有向图中有多少条不相交的路径?
具体描述为
在有向图中能够取出多少条,没有公共点的,长度为LL 的路径?

Acwing2180
Acwing2180

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

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int A[maxn], L = 0, n, 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 g[maxn];
void dp() {
L = 0;
for (int i = 1; i <= n; i++) {
g[i] = 1;
for (int j = 1; j < i; j++) {
if (A[j] <= A[i]) g[i] = max(g[i], g[j] + 1);
}
L = max(L, g[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 main() {
freopen("input.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
S = 0, T = 2*n + 2;

// dp
dp();
printf("%d\n", L);

if (L == 1) {
printf("%d\n%d\n", n, n);
return 0;
}

// build graph
for (int i = 1; i <= n; i++) {
add(i, n+i, 1);
if (g[i] == 1) add(S, i, 1);
if (g[i] == L) add(n+i, T, 1);

for (int j = 1; j < i; j++) {
if (A[j] <= A[i] && g[i] == g[j] + 1) add(n+j, i, 1);
}
}

// solve
int res = dinic();
printf("%d\n", res);
for (int i = 2; i <= idx; i++) {
int a = ver[i^1], b = ver[i];
if (a == S && b == 1) e[i] = inf;
if (a == 1 && b == n+1) e[i] = inf;
if (a == n+n && b == T) e[i] = inf;
if (a == n && b == n+n) e[i] = inf;
}
res += dinic();
printf("%d\n", res);
}

源汇不确定时还原现场

有时候最大流问题需要我们枚举源点和汇点
此时每次枚举完毕的时候,要还原现场

  • 对于边eE[idx]e \in E[\cdots \text{idx}]e[i]e[i] 的流量f|f|e[i1]e[i \oplus 1] 的容量c|c|
  • dinic\text{dinic} 算法维护的是残量网络GfG_f,最开始流量为00

所以还原现场22 步即可,注意残量网络中e=c(u,v)e = c(u, v),边维护的是容量
对于所有的边for eiE[idx]\textbf{for} \ \forall e_i \in E[\cdots \text{idx}]

  • 反向边容量退流e[i]e[i]+e[i1]e[i] \leftarrow e[i] + e[i \oplus 1]
  • 正向边流量清空,正向边流量等于反向边容量,所以e[i1]0e[i \oplus 1] \leftarrow 0

Acwing2278

  • 对于冰块uu,它的每一条出边ii,必须满足eimu\sum e_i \leqslant m_u
    很自然地想到拆点,u(u1,u2),e(u1,u2)=muu \to (u_1, u_2), \quad e(u_1, u_2) = m_u
  • 冰块(u,v)(u, v) 之间能够互相跳到,充要条件是dist(u,v)D\text{dist}(u, v) \leqslant D
    由于(u,v)(u, v) 这条路径上可以允许无数企鹅经过
    (注意,对起跳终点vv 并没有限制,对起点的限制已经加在拆点上了)
    添加边c(u,v)=, c(v,u)=,u,vc(u, v) = \infty, \ c(v, u) = \infty, \quad u, v 是拆点后的
  • 考虑源点,对于所有有企鹅的冰块,for i,ni>0\textbf{for} \ \forall i, \quad n_i > 0:
    c(S,i)=nic(S, i) = n_i
  • 枚举每一个汇点T[1n]T \in [1 \cdots n],枚举前记得还原现场,如果
    dinic(S,T)=tot,res++\textbf{dinic}(S, T) = tot, \quad res ++
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
typedef pair<int, int> PII;
const int maxn = 210, maxm = (210 + 210 + 210*210) * 2;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int n, S = 0, T, tot = 0;
double D;
PII ice[maxn];

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;
}

bool check(const PII &a, const PII &b) {
double dx = a.first - b.first, dy = a.second - b.second;
return dx*dx + dy*dy <= D*D + eps;
}

void init() {
memset(head, 0, sizeof head);
idx = 1;
tot = 0;
}

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() {
int cnt = 0;
for (int i = 1; i <= n; i++) {
T = i;
for (int k = 2; k <= idx; k += 2) {
e[k] += e[k^1];
e[k^1] = 0;
}
int res = dinic();
if (res == tot) {
cnt++;
printf("%d ", i-1);
}
}
if (cnt == 0) printf("-1\n");
else printf("\n");
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
cin >> kase;
while (kase--) {
init();
scanf("%d%lf", &n, &D);
S = 0;
// ice
for (int i = 1; i <= n; i++) {
int x, y, _n, _m;
scanf("%d%d%d%d", &x, &y, &_n, &_m);
ice[i] = {x, y};
add(i, n+i, _m);
add(S, i, _n);
tot += _n;
}
// link node
for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
if (check(ice[i], ice[j])) {
add(n+i, j, inf);
add(n+j, i, inf);
}
}

// then solve
solve();
}
}