$dinic$

前向星建图，便于找反边（编号^$1$），$bfs$给图分层，让他只能流入更低的层，顺便判断出图是否已经阻断无法再流向汇点，$head$每次复制一份，复制出的那一份每次遍历过一条已经被阻塞的边，就直接跟着$next$改到直接指向下一条边，$bfs$时再重新改回初始状态，这是和复杂度的正确性有关的，防止在单点处被卡成$O(E^2)$，$dfs$返回值是这一次又松弛出多少流量。

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
ll bfs() {
    queue<int> q;
    fp(i, 1, n * 2 * k) dep[i] = inf, nh[i] = head[i];
    dep[s] = 0;
    q.push(s);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            if (e[i].w && dep[e[i].to] == inf)
                dep[e[i].to] = dep[x] + 1, q.push(e[i].to);
        }
    }
    // cout<<dep[t]<<endl;
    return dep[t] != inf;
}
ll dfs(ll x, ll fl) {
    // cout<<x<<endl;
    if (x == t)
        return fl;
    ll res = 0;
    for (ll& i = nh[x]; i && fl; i = e[i].next) {
        if (dep[e[i].to] == dep[x] + 1) {
            ll w = dfs(e[i].to, min(fl, e[i].w));
            fl -= w;
            res += w;
            e[i].w -= w;
            e[i ^ 1].w += w;
        }
    }
    return res;
}
//主函数内
int main(){
  while(bfs())ans+=dfs();
}

时间复杂度$O(V^2E)$