网络流算法遍历图的时候,一般必须沿着容量edges(i)>0\textbf{edges}(i) > 0 的边走

Dinic 算法

dinic
Acwing2172

  • dinic(u, limit)\bold{dinic}(u, \ limit) 算法沿分层图推进
  • 推进过程要求增广路存在,也就是检查的边cf(i)>0c_f(i) > 0 容量必须大于00
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
const int maxn = 10000 + 10, maxm = 200000 + 10;
const int inf = 0x3f3f3f3f;
int n, m, S, T;
int head[maxn], edges[maxm], ver[maxm], ne[maxm], tot = 1;

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

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 && edges[i]) {
cur[y] = head[y];
d[y] = d[x] + 1;
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

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

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

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &n, &m, &S, &T);
while (m--) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
add(u, v, c);
add(v, u, 0);
}

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

三个优化

  • 流量剪枝limit>flowlimit > flow
  • 当前弧优化
  • 废点优化if t=0:d(v)=1\textbf{if} \ t = 0: d(v) = -1

最大二分匹配问题

问题描述

给定一个无向图G=(V,E)G = (V, E),一个匹配是边的一个子集MEM \subseteq E
使得对于所有节点vV\forall v \in V,子集MM 中最多有一条边与vv 相连

对于节点vv,在子集MM 中有边与vv 相连,则称节点vv 是由MM 所匹配
否则,节点vv 是没有匹配的
最大匹配MM,即对于任意匹配MM',均有MM|M| \geqslant |M'|

寻找最大二分匹配

binpart
初步分析如下

  • 每个节点至少有一条相连的边,所以EV/2|E| \geqslant |V|/2
  • EE=E+V3E|E| \leqslant |E'| = |E| + |V| \leqslant 3|E|

所以E=Θ(E)|E'| = \Theta (E)

引理
G=(V,E)G = (V, E) 是一个二分图,其节点划分是V=LRV = L \cup R,不妨设G=(V,E)G' = (V', E')
是图GG 对应的流网络。如果MMGG 中的一个匹配,则在流网络GG' 中存在一个整数值的流ff
使得f=M|f| = |M|。相反,如果ffGG' 中的一个整数值的流,同样在GG 中存在一个匹配MM
使得M=f|M|=|f|

  • 已知图GG 的一个匹配MM,可以定义流ff 如下
    • 如果边(u,v)Mf(s,u)=f(u,v)=f(v,t)=1(u, v) \in M \Longrightarrow f(s, u) = f(u, v) = f(v, t) = 1
      而其他属于EE' 的边(u,v)(u, v),定义f(u,v)=0f(u, v) = 0
    • 另一方面,对于任意节点 v\forall \ v,因为MM 最多只有一条边与vv 相连,
      所以子集MM 中的边所诱导的路径suvts \to u \to v \to t 是节点不相交的
      横跨切割{L{s},R{t}}\{L \cup \{s\} , R \cup \{t\}\} 的净流量等于MMM=f|M| = |f|
  • ffGG' 中的一个整数值的流,并且设

    M={(u,v):uL,vR,并且 f(u,v)>0}M = \{(u, v): u \in L, v \in R, \text{并且 } f(u, v) > 0\}

    • 每个节点uLu \in L 仅有一条进入的边(s,u)(s, u),容量为11,也就是说最多有11 单位流量流入
    • 根据流量守恒,离开节点的流也必须有11 个单位的流量,因为f|f| 为整数,
      所以11 单位的流量只能最多从11 条边流出
      存在vRv \in R,使得f(u,v)=1f(u, v) = 1,并且uu 的出边中仅有11 条带有正的权值
      由此,集合MM 是一个匹配
    • uL,f(s,u)=1\forall u \in L, f(s, u) = 1,并且(u,v)EM(u, v) \in E-Mf(u,v)=0f(u, v) = 0
      横跨切割(L{s},R{t})(L \cup \{s\}, R \cup \{t\}) 的净流量f(L{s},R{t})=Mf(L \cup \{s\}, R \cup \{t\}) = |M|
      由此M=f|M|=|f|

推论
二分图GG 中的一个最大匹配MM 的基数等于其对应的流网络GG' 中的某一最大流f|f| 的值

如果MM 是最大匹配,但f|f| 不是最大流,那么存在一个最大流f>f|f'| > |f|
而根据引理,此时ff' 对应原来二分图的一个匹配MM',其基数为
M=f>f=M|M'| = |f'| > |f| = |M| 这与MM 是一个最大匹配矛盾

同样,如果ffGG' 中的一个最大流,其对应的匹配是GG 的一个最大匹配

Acwing2175

  • 方案输出,可以遍历所有的正向边
  • 如果发现边的容量为00,那么说明这个边被用到了,构成了一组方案
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
const int maxn = 100 + 10, maxm = 6000 + 10;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], ne[maxm], tot = 1;
int n, m, S, T;

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

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] > 0) {
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 (true) {
flow = dinic(S, inf);
if (flow == 0) break;
res += flow;
}
}
return res;
}

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

// then solve
printf("%d\n", dinic());
for (int i = 2; i <= tot; i += 2) {
if (ver[i] > m && ver[i] <= n && e[i] == 0) {
printf("%d %d\n", ver[i^1], ver[i]);
}
}
}

二分图的多重匹配

Acwing2179
Acwing2179

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
const int maxn = 430, maxm = (150 * 270 + maxn) * 2;
const int inf = 0x3f3f3f3f;
int tot = 0, n, m, 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 cur[maxn], d[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;
}

void out() {
for (int u = 1; u <= m; u++) {
for (int i = head[u]; i; i = ne[i]) {
if (ver[i] > m && ver[i] <= n+m && !e[i]) printf("%d ", ver[i]-m);
}
printf("\n");
}
}

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

// then dinic
if (dinic() != tot) {
printf("0\n");
return 0;
}

printf("1\n");
out();
}

无源汇上下界可行流

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

int head[maxn], ver[maxm], e[maxm], ne[maxm], L[maxm], idx = 1, tot = 0;
int n, m, S, T, delta[maxn];
void add(int a, int b, int c, int d) {
ver[++idx] = b; e[idx] = d-c; L[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;
}

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, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
delta[a] -= c, delta[b] += c;
}
for (int i = 1; i <= n; i++) {
if (delta[i] > 0) add(S, i, 0, delta[i]), tot += delta[i];
else if (delta[i] < 0) add(i, T, 0, -delta[i]);
}
//debug(tot);

if (dinic() != tot) {
puts("NO");
return 0;
}
puts("YES");
for (int i = 2; i < 2 + m*2; i += 2) {
printf("%d\n", e[i^1] + L[i]);
}
}

有源汇上下界最大流

循环流与具有下界的流
[2020]Douglas B.West, Introduction to Graph Theroy, Second Edition(图论导引 原书第二版)\text{[2020]}\quad \text{Douglas B.West, Introduction to Graph Theroy, Second Edition(图论导引 原书第二版)}
chapter 4, 定理4.3.20\text{chapter 4},\ \textbf{定理4.3.20}

  • 原网络GG 添加从tst \to s 的具有++\infty 容量的边,此时的网络有个处处守恒的可行流
    称为循环流
  • 对于可行循环流CC,在所有节点处引入供应量σ(xi)\sigma (x_i) 和需求量(xi)\partial (x_i),给定流量约束
    l(e)f(e)u(e)l(e) \leqslant f(e) \leqslant u(e),在每一条边上令c(e)=u(e)l(e)c(e) = u(e) - l(e)
    f+(v)f^{+}(v) 表示离开vv 的总流量,f(v)f^{-}(v) 表示进入vv 的总流量

    l(v)=e[V(C)v,v]l(e)l+(v)=e[v,V(C)v]l(e)b(v)=l(v)l+(v)\begin{gathered} l^{-}(v) = \sum_{e \in [V(C)-v, v]} l(e) \\ l^{+}(v) = \sum_{e \in [v, V(C)-v]} l(e) \\ b(v) = l^{-}(v) - l^{+}(v) \end{gathered}

    l(v)vl+(v)\cdots \xrightarrow{l^{-}(v)} v \xrightarrow{l^{+}(v)} \cdots

  • 由于可行循环流流量处处守恒,所以b(v)=0\sum b(v) = 0,一个循环可行流在每个顶点满足
    f+(v)f(v)=0f^{+}(v) - f^{-}(v) = 0,令f(e)=f(e)l(e)f'(e) = f(e) - l(e)

    {f+(v)=f+(v)l+(v)f(v)=f(v)l(v)\begin{cases} f'^{+}(v) = f^{+}(v) - l^{+}(v) \\ f'^{-}(v) = f^{-}(v) - l^{-}(v) \end{cases}

    可以推出

    {l(v)=f(v)f(v)l+(v)=f+(v)f+(v)f+(v)=f(v)\begin{cases} l'^{-}(v) = f^{-}(v) - f'^{-}(v) \\ l'^{+}(v) = f^{+}(v) - f'^{+}(v) \end{cases} \xrightarrow{f^{+}(v) = f^{-}(v)}

    所以有

    l(v)l+(v)=b(v)=f+(v)f(v)l^{-}(v) - l^{+}(v) = b(v) = f'^{+}(v) - f'^{-}(v)

    也就是说,ffCC 中的一个可行流当且仅当
    ff' 满足流量约束0f(e)c(e)0 \leqslant f'(e) \leqslant c(e)
    并且在每个顶点处满足f+(v)f(v)=b(v)f'^{+}(v) - f'^{-}(v) = b(v)
  • 这样可以将循环流问题转换为一个供应量和需求量的问题,为了满足流量守恒
    • b(v)0b(v) \geqslant 0,那么vv 向网络供应流量b(v)|b(v)|
      建立一个超级源点SS,令容量c(S,v)=b(v)c(S, v) = |b(v)|
    • b(v)<0b(v) < 0,则vv 对网络有b(v)|b(v)| 的需求量
      建立一个超级汇点TTc(v,T)=b(v)c(v, T) = |b(v)|
  • 这样我们构造出了新网络GG,并且之前已经证明了
    CC 有一个可行循环流ff 当且仅当GG 有一个满流浸润了离开SS 或进入TT 的所有边
    此时我们称GG 保持一个浸润状态

algorithm\textbf{algorithm}

  • 根据上述方法在原网络GG 的基础上,建立超级源点SS 和 超级汇点TT,来满足供需关系
  • 在原网络GG 的汇点tt 和 源点ss 中,连一条边使得c(t,s)=+c(t, s) = +\infty
    此时构造出可行循环流网络,新网络记为NN
  • dinic(N)\textbf{dinic}(N) 判断新网络是否浸润
  • 如果浸润,在浸润状态下NN 的一个可行流记为f0f_0
    那么f0f_0 中从sts \to t 的流量f0(st)=e(ts)f_0(s \to t) = e(t \to s)
    e(ts)e(t \to s) 表示执行完dinic\textbf{dinic} 之后,边(t,s)(t, s) 的容量
  • 去掉循环流的边(t,s)(t, s),再次执行dinic\textbf{dinic} 算法,使得sts \to t 没有增广路
    f=dinic(s,t)f' = \bold{dinic}(s, t),表示执行增广能够增加的流量为ff'
    则此时(f0f)=f(f_0 \uparrow f') = fff 即为sts \to t 的上下界最大流

下面来证明这个算法的正确性
cycle-01
cycle-02

注意,这里对于浸润流f0f_0f0(st)f_0(s \to t) 的流量是分散的(因为sts \to t 的路径上可能有很多点)
f0(ts)f_0(t \to s) 是可以直接求的,因为我们在残量网络上连了一条ts, c(t,s)=+t \to s, \ c(t, s) = +\infty 的边
因为f0(st)=f0(ts)=c(s,t)f_0(s \to t) = f_0(t \to s) = c(s, t),所以求出f0f_0 之后
只需要在残量网络中找到表示edge(s,t)\textbf{edge}(s, t) 这条边,即表示f0(st)f_0(s \to t)

Acwing2189

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

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1, tot = 0;
int A[maxn];
int n, m, s, t, 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;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &n, &m, &s, &t);
S = 0, T = n+1;

for (int i = 0; i < m; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, d-c);
A[a] -= c, A[b] += c;
}
for (int i = 1; i <= n; i++) {
if (A[i] > 0) tot += A[i], add(S, i, A[i]);
else if(A[i] < 0) add(i, T, -A[i]);
}
add(t, s, inf);

// then solve
if (dinic() != tot) {
puts("No Solution");
return 0;
}

int res = e[idx];
e[idx] = e[idx-1] = 0;
S = s, T = t;
int ans = res + dinic();
printf("%d\n", ans);
}

有源汇上下界最小流

之前已经证明过

f0+f(st)=f(st)|f_0| + |f'(s \to t)| = f(s \to t)

所以fmax(st)=f0+max{f(st)}f_{\max}(s \to t) = |f_0| + \max \{f'(s \to t)\}fmin(st)=f0+min{f(st)}f_{\min}(s \to t) = |f_0| + \min \{f'(s \to t)\}
由于f(st)=f(ts)f'(s \to t) = -f'(t \to s),所以
min{f(st)}=max{f(ts)}\min \{f'(s \to t)\} = - \max \{f'(t \to s)\}

  • 于是我们求出浸润流f0f_0 之后,在残量网络中求一遍tst \to s 的最大流
  • ans=f0dinic(t,s)\textbf{ans} = f_0 - \textbf{dinic}(t, s)

多源汇最大流

algorithm\textbf{algorithm}

  • 建立一个超级源点SS,对于所有源点for  si\textbf{for} \ \forall \ s_i
    建立一条容量\infty 的边,即c(S,si)=c(S, s_i) = \infty
  • 同时对于所有汇点,建立超级汇点TT,使得c(ti,T)=c(t_i, T) = \infty
  • 原网络的最大流等于f(S,T)f(S, T),即STS \to T 的最大流

proof\textbf{proof}

  • 对于新图GG' 的一个可行流,它一定是原图的一个可行流,因为除了S,TS, T
    其余的点都满足容量限制和流量守恒
  • 对于原图GG 的一个可行流ff,对于v{V{si,ti,S,T}}v \in \{V - \{s_i, t_i, S, T\}\}
    它一定满足容量限制和流量守恒,于此同时,我们可以通过f(S,si), f(ti,T)f(S, s_i), \ f(t_i, T)
    来补偿从sis_i 流向网络的流量,使得所有si,tis_i, t_i 也满足流量守恒
    另外由于c(S,si)=, c(ti,T)=c(S, s_i) = \infty, \ c(t_i, T) = \infty,容量限制也一定满足
    所以对于新图GG' 来说,ff 诱导的流ff' 也一定是一个可行流

Acwing2234

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
const int maxn = 10000 + 10, maxm = (100000 + maxn) * 2;
const int inf = 0x3f3f3f3f;
int n, m, sc, tc, 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);
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;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &n, &m, &sc, &tc);
S = 0, T = n+1;
while (sc--) {
int x;
scanf("%d", &x);
add(S, x, inf);
}
while (tc--) {
int x;
scanf("%d", &x);
add(x, T, inf);
}
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", dinic());
}