%%% y 总 欢迎大佬来指出错误 谢谢大佬啦

Dinic算法

while(){
    一次找多条增广路，通过分层图;
    更新残留网络
}

1、当前弧优化

2号优化 (不知道叫什么名字)

3号优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, cur[N], d[N], q[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 找增广路 同时将图变成分层图，方便处理环
int bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    d[S] = 0, q[0] = S, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            if(w[i] && d[e[i]] == -1){
                d[e[i]] = d[u] + 1;
                cur[e[i]] = h[e[i]];
                if(e[i] == T)   return 1;
                q[++ tt] = e[i];
            }
        }
    }
    return 0;
}
// 更新残留网络
int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0, k;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i; // 当前弧优化
        if(w[i] && d[e[i]] == d[u] + 1){
            k = dfs(e[i], min(flow - rest, w[i]));
            if(!k)  d[e[i]] = -1; // 3号优化，将分层图中的当前点变成 -1 相当于打上标记
            w[i] -= k, w[i ^ 1] += k, rest += k;
            if(rest == flow)    return flow; // 2号优化
        }
    }
    return rest;
}

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

int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, 0);
    }

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

    return 0;
}

最大流之上下界可行流

无源汇上下界可行流

首先假设有一个网络流，它满足题目的要求，且满足条件。
$$ 1、流量守恒 \\\\ 2、c_{low}(u, v) \le f(u, v) \le c_{up}(u, v) $$

但是这个网络流不满足一般性质，所以需要进行一些修改，并构建一个新的图。
$$ c_{low}(u, v) \le f(u, v) \le c_{up}(u, v) \\\\ => 0 \le f(u, v) - c_{low}(u, v) \le c_{up}(u, v) - c_{low}(u, v) 它满足了我们的一般性质 \\\\ 令 g(u, c) = f(u, v) - c_{low}(u, v)并构建一个新的图 $$

通过观察发现这个新图因为每条边都减去了容量的下届所以此时的可行流不再满足流量守恒了。所以需要对每个点进行一些操作让它满足流量守恒。
$$ 首先记 c_{x出} = \sum_{(v \in V)}c_{low}(x, v)[(x, v) \in E] \\\\ c_{x入} = \sum_{(v \in V)}c_{low}(v, x)[(v, x) \in E] \\\\ f_{x入} = \sum_{(v \in V)}f(v, x)[(v, x) \in E] (注意这个f的值是对于原网络中的可行流) \\\\ f_{x出} = \sum_{(v \in V)}f(x, v)[(x, v) \in E] (注意这个f的值是对于原网络中的可行流) $$

$$ 当 c_{x入} > c_{x出} => f_{x入} - c_{x入} < f_{x出} - c_{x出} \\\\ 此时就需要建立一个超级源点向当前 x 点连一条边 容量为 c_{x入} - c_{x出} 来保证流量守恒 \\\\ 当 c_{x入} < c_{x出} => f_{x入} - c_{x入} > f_{x出} - c_{x出} \\\\ 此时就需要建立一个超级汇点，从当前 x 点连一条边到汇点 容量为 c_{x出} - c_{x入} 来保证流量守恒 \\\\ $$
通过操作完之后的图变成了

此时对这个图进行跑最大流 如果能够跑满流(也就是 每一条 f(S, v) == c(S, v)) 那么就存在了一种可行解。

证明：
$$ 1、容量限制 \\\\ 对于原图 => c_{low}(u, v) \le f(u, v) \le c_{up}(u, v) \\\\ 对于新图 => 0 \le f(u, v) - c_{low}(u, v) \le c_{up}(u, v) - c_{low}(u, v) $$

$$ 2、流量守恒 \\\\ 因为进行了一系列操作同时又从源点出发的每条边都能跑满流到汇点，这样就满足了流量守恒。 $$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = (10200 + N) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx, l[M];
int n, m, S, T, d[N], cur[N], q[N], A[N];

void add(int a, int b, int c, int d)
{
    e[idx] = b, w[idx] = d, l[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 1, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            if(w[i] && !d[e[i]]){
                cur[e[i]] = h[e[i]];
                d[e[i]] = d[u] + 1;
                if(e[i] == T)   return 1;
                q[ ++ tt] = e[i];
            }
        }
    }
    return 0;
}

int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0, k;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i;
        if(w[i] && d[e[i]] == d[u] + 1){
            k = dfs(e[i], min(flow - rest, w[i]));
            if(!k)  d[e[i]] = 0;
            w[i] -= k;
            w[i ^ 1] += k;
            rest += k;
            if(rest == flow)    return flow;
        }
    }
    return rest;
}

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

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

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

    return 0;
}

有源汇上下界最大流

首先我们可以先和上面的题目进行一个转化 然后发现这其中有源点和汇点是不满足流量守恒性质的。所以我们可以通过连一条汇点到源点的边 容量为无穷大。

然后我们通过上面的转化成一个新图。

现在我们假设新图中从 超级源点 S 出去的边都能够跑满流。然后我们面临的一个问题是如何求最大流。

首先我们记
$$ f’ 为原图(第一个图)的一个可行流\\\\ f_{0}’ 为新图(第二个图)的一个可行流 \\\\ f_{0s->t}’为新图中 s 到 t 的可行流 $$
下图为原图的一个可行流。
$$ f’ = 6 $$

下图为新图的一个满流。其中
$$ f_{0}’ = 5 \\\\ f_{0s->t}’ = f(t, s) = 4 $$

然后我们在新图的当前的残留网络中去掉 超级源点 S 和 超级汇点 T。并且记当前的可行流
$$ f_{s->t}’ 为残留网络的一个可行流 \\\\ 比如下面图的f_{s->t}’= 2 $$

通过观察可以发现
$$ f’ = f_{0s->t}’ + f_{s->t}’(其中S->1->2->T的一条增广路是我们通过操作添加的不是s->t的一个增广路径) $$
现在需要证明一下原图中的一个可行流是可以和残留网络中的可行流可以一一对应也就是
$$ f’ 可以和 f_{s->t}’一一对应 $$
首先我们已经知道了
$$ f_{0}’ 是和 f’一一对应的 $$
证明右边能够对应到左边

我们通过将残留网络加入到新图的满流中去
$$ 得到式子|f_{s->t}’ + f_{0}’|\\首先它一定满足容量限制 \\\\ 又因为残留网络中任何s->t的流量都可以通过 t->s 的容量为无穷的边流回去所以此时也满足流量守恒 \\\\ 因为残留网络中任何s->t的流量都可以通过 t->s 的容量为无穷的边流回去，也就是此时的f_{s->t}’ = 0 \\\\ 所以 |f_{s->t}’ + f_{0}’| = f_{0}’ $$

$$ 因为 f_{0}’ 可以和 f’一一对应所以|f_{s->t}’ + f_{0}’|可以和f’一一对应 \\\\ 又因为 f_{0}’是固定的所以f_{s->t} 可以和 f’对应 $$
证明左边能够对应右边(我觉得这非常的恰好 可能是我理解错了)
$$ 记f’‘ = |f_{s->t}’ + f_{0}’| \\\\ 我们通过在|f_{s->t}’ + f_{0}’|中得到图中减去新图的满流 \\\\ 得到式子 |f’‘ - f_{0}’| = f_{s->t}’\\\\ 首先它也一定是满足容量限制的 \\\\ 同时又因为新图中原先只有超级源点和超级汇点不满足流量守恒 \\\\ 但是因为减去满流之后 此时超级源点和超级汇点的流量都是0 \\\\ 所以此时的新图也满足流量守恒。 \\\\ f’ = |f_{s->t}’ + f_{0}’| = f’‘ \\\\ |f’ - f_{0}’| = f_{s->t}’\\\\ 因为满流 f_{0}’ 是一个固定的值所以 f’ 可以和 f_{s->r}’对应 $$

最后我们要让
$$ f’ = f_{0s->t}’ + f_{s->t}’最大也就是f_{s->t}’最大 $$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = (N + 10000) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, d[N], cur[N], q[N], s, t, A[N];

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

int bfs()
{
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 1, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            if(w[i] && !d[e[i]]){
                d[e[i]] = d[u] + 1;
                cur[e[i]] = h[e[i]];
                q[++ tt] = e[i];
                if(e[i] == T)   return 1;
            }
        }
    }
    return 0;
}

int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0, k;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i;
        if(w[i] && d[e[i]] == d[u] + 1){
            k = dfs(e[i], min(flow - rest, w[i]));
            if(!k)  d[e[i]] = 0;
            w[i] -= k, w[i ^ 1] += k, rest += k;
            if(rest == flow)    return flow;
        }
    }
    return rest;
}

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

int main()
{
    cin >> n >> m >> s >> t;
    memset(h, -1, sizeof h);
    S = 0, T = n + 1;
    for(int i = 1; i <= m; i ++ ){
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        add(a, b, d - c);
        add(b, a, 0);
        A[a] -= c, A[b] += c;
    }

    int tot = 0;
    for(int i = 1; i <= n; i ++ ){
        if(A[i] > 0)    add(S, i, A[i]), add(i, S, 0), tot += A[i];
        else if(A[i] < 0)   add(i, T, -A[i]), add(T, i, 0);
    }

    add(t, s, inf), add(s, t, 0);

    if(dinic() < tot)  puts("No Solution");
    else{
        int res = w[idx - 1];
        S = s, T = t;
        w[idx - 1] = w[idx - 2] = 0;
        printf("%d\n", res + dinic());
    }

    return 0;
}

有源汇上下界最小流

根据公式
$$ f’ = f_{0s->t}’ + f_{s->t}’ \\\\ 其中 f_{s->t}’ = - f_{t->s}’ \\\\ f’ = f_{0s->t}’- f_{t->s}’ \\\\ 要使 f’ 最小也就是 f_{t->s}’ 最大 $$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 50010, M = (N + 125010) * 2, inf = 0x3f3f3f3f;

int n, m, S, T, s, t, d[N], cur[N], q[N], A[N];
int h[N], ne[M], e[M], w[M], idx;

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

int bfs()
{
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 1, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            if(w[i] && !d[e[i]]){
                d[e[i]] = d[u] + 1;
                cur[e[i]] = h[e[i]];
                q[++ tt] = e[i];
                if(e[i] == T)   return 1;
            }
        }
    }
    return 0;
}

int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0, k;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i;
        if(w[i] && d[e[i]] == d[u] + 1){
            k = dfs(e[i], min(flow - rest, w[i]));
            if(!k)  d[e[i]] = 0;
            w[i] -= k;
            w[i ^ 1] += k, rest += k;
            if(rest == flow)    return flow;
        }
    }
    return rest;
}

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

int main()
{
    cin >> n >> m >> s >> t;
    memset(h, -1, sizeof h);
    S = 0, T = n + 1;
    for(int i = 1; i <= m; i ++ ){
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        add(a, b, d - c), add(b, a, 0);
        A[a] -= c, A[b] += c;
    }

    int tot = 0;
    for(int i = 1; i <= n; i ++ ){
        if(A[i] > 0)    add(S, i, A[i]), add(i, S, 0), tot += A[i];
        else if(A[i] < 0)   add(i, T, -A[i]), add(T, i, 0);
    }
    add(t, s, inf), add(s, t, 0);

    if(dinic() < tot)   puts("No Solution");
    else{
        int res = w[idx - 1];
        S = t, T = s;
        w[idx - 1] = w[idx - 2] = 0;
        printf("%d\n", res - dinic());
    }

    return 0;
}

多源汇最大流

建立一个超级源点向每个源点连容量是无穷的边 ， 建立一个超级汇点每个汇点向超级汇点连一条边。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10, M = (N + 1e5 + 10) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, sc, tc, d[N], cur[N], q[N];

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

int bfs()
{
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 1, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            if(w[i] && !d[e[i]]){
                d[e[i]] = d[u] + 1;
                cur[e[i]] = h[e[i]];
                q[++ tt] = e[i];
                if(e[i] == T)   return 1;
            }
        }
    }
    return 0;
}

int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0, k;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i;
        if(w[i] && d[e[i]] == d[u] + 1){
            k = dfs(e[i], min(flow - rest, w[i]));
            if(!k)  d[e[i]] = 0;
            w[i] -= k, w[i ^ 1] += k, rest += k;
            if(rest == flow)    return flow;
        }
    }
    return rest;
}

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

int main()
{
    cin >> n >> m >> sc >> tc;
    memset(h, -1, sizeof h);
    S = 0, T = n + 1;
    for(int i = 1; i <= sc; i ++ ){
        int x;
        scanf("%d", &x);
        add(S, x, inf), add(x, S, 0);
    }
    for(int i = 1; i <= tc; i ++ ){
        int x;
        scanf("%d", &x);
        add(x, T, inf), add(T, x, 0);
    }
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, 0);
    }

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

    return 0;
}

最大流之关键边

一个网络的最大流对应的残留网络中的关键边满足条件
$$ f(u, v) = c(u, v) \\\\ 存在 源点S 到 u 的路径其中每条边的f < c(流量小于容量) \\\\ 存在v到汇点T的路径其中每条边的f<c(流量小于容量) $$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = (N + 5010) * 2, inf = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
int n, m, S, T, d[N], cur[N], q[N];
bool vis_s[N], vis_t[N];

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

int bfs()
{
    memset(d, 0, sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 1, cur[S] = h[S];
    while(hh <= tt){
        int u = q[hh ++ ];
        for(int i = h[u]; ~i; i = ne[i]){
            if(w[i] && !d[e[i]]){
                d[e[i]] = d[u] + 1;
                cur[e[i]] = h[e[i]];
                q[ ++ tt] = e[i];
                if(e[i] == T)   return 1;
            }
        }
    }
    return 0;
}

int dfs(int u, int flow)
{
    if(u == T)  return flow;
    int rest = 0, k;
    for(int i = cur[u]; ~i; i = ne[i]){
        cur[u] = i;
        if(w[i] && d[e[i]] == d[u] + 1){
            k = dfs(e[i], min(flow - rest, w[i]));
            if(!k)  d[e[i]] = 0;
            w[i] -= k, w[i ^ 1] += k, rest += k;
            if(rest == flow)    return flow;
        }
    }
    return rest;
}

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

void dfs(int u, bool st[], int t)
{
    st[u] = 1;
    for(int i = h[u]; ~i; i = ne[i]){
        if(w[i ^ t] && !st[e[i]]){
            dfs(e[i], st, t);
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    S = 1, T = n;
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a ++, b ++ ;
        add(a, b, c), add(b, a, 0);
    }

    dinic();

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

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

    return 0;
}