关于网络流

这个东西吧，博大精深，有的题你看着像dp，或者像膜你题，但是又怎么想都想不出来，最后看算法tag发现这玩意竟然是网络流¿

总之就是很多看似难解、限制很多的题可以建出网络流的模型求解

最大流

网络流的模型可以抽象为水管，有一个水源，n-2个中转站，一个要送去水的目的地，每个站点都有若干个水管与其他站点相连，但是水管有粗细，每秒能通过的最大流量也不一样，求目的地每秒最多接收到多少流量。

其中，水管和中转站就是网，水流就是流，我们就得到了网络流。（上面求的就是源点到汇点的最大流。

给出一张非常经典的图：

这个图很容易看出来最大流走 1->2->4 和 1->3->4 ，最大流为22。

对于程序实现，我们只知道边的最大流量还不行，还得知道现在这条边能再增加多少流量，即剩下的流量，这个剩下的流量就叫做 残量，由边的残量构成的图就叫 残量图，如果残量为00，那么就相当于一条断边。

在残量图上，如果我们从源点开始沿着某一条路径到达了汇点，说明这一条路上的流量还可以增加，我们就把这条路叫做 增广路。

如上图，我们可以从11开始 dfs，假设我们 dfs 到的结果是 1->2->3->4 ，我们就得到了这条增广路，将其每条边都减去流量11，我们就得到了一个残量图：

但是此时已经没有增广路了，跟我们预期的结果不一样，我们发现，是因为程序走了 2->3 这条边抢了其他增广路的流量，我们怎么解决这个问题呢？有两个方法：

  1. 写个AI，深度学习一手，拿个数据生成器就往AI里跑，然后调AI，最后调成不会走错误路线的超级AI，自动暴切网络流

  2. 考虑实际情况，我们是OI选手，我们需要一个在考场上能用的解决方案，所以我们需要让程序在走错边时可以反悔，但又不能仅仅只是反悔，因为上图中 3->4 也是答案的一部分，如果走错边就反悔的话会 T 飞，我们得想办法只把 2->3 这条边反悔，这时就需要引入反向边了。

首先，这个反向边不只是单单建个边就完事了，我们的目的是让程序反悔，让程序跑到33时再跑回22让错误路径中 2->3 这部分浪费掉的流量给要回来，所以我们这么处理反向边：

设原边的最大容量为 maxflow , 正边的残量为 flow ，反边的残量为 rflow ，则有 flow + rflow = maxflow ，通俗来讲就是把正边流走的流量加到反边上去而不是直接消失，正反边的流量和为原最大容量

设某一条增广路的流量为aa，则对于这条增广路上的每个边，都有 flow -= a ， rflow += a ，感性理解一下，这条反向边就是为了防止走错，把正向边走的流量转移到反向边上去，再走反向边时就相当于反悔

我们有了反向边之后，上面那张图就变成了这样：

对这个图继续寻找增广路，我们就可以找到 1->3->2->4 这条增广路，最终答案为22，与正确答案一样。

为什么这样就是对的呢？因为作了反向边处理之后，我们没走 2->3 这条路，分析一下这两条增广路：1->2->3->4， 1->3->2->4 ，我们把每一条边都拆出来，发现走了一个 2->3 和一个 3->2 ，就相当于没走，把剩下的边拼一块，我们就得到了 1->2->4 和 1->3->4 ，即得到了正确答案

有一条很显然的结论：当网络图中没有增广路时，此时的流就是最大流

证明吧…大概就是没有增广路之后我们无法反悔任何一条边来获取更大流量，所以已经是最大流了

严谨的证明请自己去bdfs论文，我太菜了只能这么解释XD

这里的反向边的实现不需要很复杂，我们可以利用成对边的思想，将链式前向星中数组下标从2开始，这样 i^1 就可以得到与 i 成对的那条边，即反边

以下的代码都里用S和T代表源点和汇点

Edmonds-Karp算法

但是有了反向边又有了一个问题：我们需要保证程序不犯傻，别走了 1->2 再走 2->1 搁这原地tp。解决办法也很简单，我们可以进行bfs，走过的点标记一遍，保证不会反着走，并计算流量和前驱，直到走到汇点或者图上无增广路为止。

这个每次bfs找一条增广路进行增广的算法就是Edmonds-Karp(EK)算法

#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
#define N 114514
#define M 1919810
typedef long long ll;

namespace graph
{
    struct edge{
        int from, to, flow, next;
    }side[M*2];
    int head[N], ccnt = 1;
    void insert(int from, int to, int flow)
    {
        side[++ccnt] = {from, to, flow, head[from]}; head[from] = ccnt;
        side[++ccnt] = {to, from, 0, head[to]}; head[to] = ccnt;
    }

    int S, T;
    int dis[N], pre[N];

    ll EK();
    bool bfs(int S, int T);
    ll dfs(int x, ll flow);
}
using namespace graph;

int n, m;

int main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; i++)
    {
        int u, v, f;
        cin >> u >> v >> f;
        insert(u, v, f);
    }
    cout << EK() << endl;
}

ll graph::EK()
{
    ll maxflow = 0;
    while(bfs(S, T))
    {
        ll minf = LLONG_MAX;
        for(int x = T; x != S; x = side[pre[x]].from)
            minf = min(minf, (ll)side[pre[x]].flow);
        for(int x = T; x != S; x = side[pre[x]].from)
        {
            side[pre[x]].flow -= minf;
            side[pre[x]^1].flow += minf;
        }
        maxflow += minf;
    }
    return maxflow;
}
bool graph::bfs(int S, int T)
{
    memset(dis, 0, sizeof(dis));
    queue<int> q; int x;
    q.push(S); dis[S] = 1;
    while(q.size())
    {
        x = q.front(); q.pop();
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and !dis[side[i].to])
            {
                dis[side[i].to] = dis[x]+1;
                pre[side[i].to] = i;
                q.push(side[i].to);
                if(side[i].to == T)
                    return true;
            }
        }
    }
    return false;
}

EK算法的最坏时间复杂度为O(nm2)O(nm^2)，但一般使用达不到这个上界，大概能解决10410^4级别的网络

Dinic算法

但是我们发现，EK算法每次bfs最坏要遍历一遍整个图，最终却只找到一条最短增广路，这样效率很低，有很大优化空间

我们每次bfs时，其实可以计算出[1,m][1,m]条增广路，我们可以用dfs进行多路增广

具体方法是：每次bfs时计算出图上每个点的深度，然后从源点开始dfs，按着深度进行增广，把当前计算出的增广路全部增广掉

其实就是计算出深度，从源点开始灌水，把能灌的路径灌完再进行下一次bfs，这样我们可以大大减少bfs遍历图的次数，提高不少效率

这样每次一个bfs和一个dfs进行多路增广的就是Dinic算法

当然最坏情况的时间复杂度也是O(nm2)O(nm^2)，但是实际应用的话能解决104,10510^4,10^5级别的网络

当前弧优化

我们可以加一个小小的优化，把最坏时间复杂度从O(nm2)O(nm^2)优化成O(n2m)O(n^2m)

为了优化，我们引入几个之前就该先引入的概念，但是因为这个对于前面的理解帮助不大，所以在这里才说

弧：其实就是一条路径
弧流量：这个弧上的流量，即弧上最小边的容量

为什么叫当前弧优化呢，我们回顾dinic的dfs，我们就相当于从源点疯狂灌水，把能灌过去的全灌的，所以之前灌过一次的地方，它的流量一定是被"榨干"的，下次再灌的时候直接跳过即可

具体做法就是定义一个当前弧数组 cur ，在每次bfs时将 head copy一份到 cur 中，然后在dfs里每次记录下在哪条边上跳出循环，把编号赋给 cur ，每次遍历一个点时就从 cur 开始而不是 head

但是这里要注意，当前弧是只针对一个分层图进行优化的，当dfs结束重新分层时，要重置 cur 数组

这样顶多遍历一遍每个点而不是每条边，成功把复杂度优化到O(n2m)O(n^2m)

dinic算法效率已经很高了，除了luogu上那个预流推进的模板题目前没找到卡dinic的题

#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
#define N 114514
#define M 1919810
typedef long long ll;

namespace graph
{
    struct edge{
        int to, flow, next;
    }side[M*2];
    int head[N], ccnt = 1;
    void insert(int from, int to, int flow)
    {
        side[++ccnt] = {to, flow, head[from]}; head[from] = ccnt;
        side[++ccnt] = {from, 0, head[to]}; head[to] = ccnt;
    }

    int S, T;
    int cur[N], dis[N];

    ll dinic();
    bool bfs(int S, int T);
    ll dfs(int x, ll flow);
}
using namespace graph;

int n, m;

int main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; i++)
    {
        int u, v, f;
        cin >> u >> v >> f;
        insert(u, v, f);
    }

    cout << dinic() << endl;
}

ll graph::dinic()
{
    ll flow = 0;
    while(bfs(S, T))
        flow += dfs(S, INF);
    return flow;
}
bool graph::bfs(int S, int T)
{
    memcpy(cur, head, sizeof(head));
    memset(dis, 0, sizeof(dis));
    queue<int> q; int x;
    q.push(S); dis[S] = 1;
    while(q.size())
    {
        x = q.front(); q.pop();
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and !dis[side[i].to])
            {
                dis[side[i].to] = dis[x]+1;
                q.push(side[i].to);
                if(side[i].to == T)
                    return true;
            }
        }
    }
    return false;
}
ll graph::dfs(int x, ll flow)
{
    if(x == T) return flow;
    ll rest = flow, k; int i;
    for(i = cur[x]; i; i = side[i].next)
    {
        if(side[i].flow and dis[side[i].to] == dis[x]+1)
        {
            k = dfs(side[i].to, min(rest, (ll)side[i].flow));
            if(!k) dis[side[i].to] = -1;
            side[i].flow -= k;
            side[i^1].flow += k;
            if(!(rest-=k)) break;
        }
    }
    cur[x] = i;
    return flow-rest;
}

最小割

割的定义：在网络流中，设源点为ss，汇点为tt，所有点的总集为VV，将图中点分成两个集合S,TS,T，s∈Ss \in S，t∈Tt \in T，且S∪T=VS \cup T = V，称其为割

割的容量：所有两端的点不属于同一个集合的边的容量的总和，就是割掉的边的容量和

求最小割就是求最小的割的容量

这里有一条定理：任意一个割大于等于任意一个流，我们来证一下：

我不会那种非常严谨、语言非常规范的证明，所以我们回到开头那个比喻，首先，一个割肯定要把所有水流切断，否则ss和tt就是联通的，水流一定小于等于水管能承载的流量，而割的容量又等于水管的容量，所以流一定小于等于割

有了这个定理，我们就可以得到： 最小割等于最大流

最小割通常适用于选择有冲突时求出最小花费或最大取值一类的题

代码就不给了，就是最大流代码

最小割的题大多数是给定一些比较恶心的限制然后让你求出一个选择方案使得选择的价值最大，一般这种题用最大流很难建出来模型，这时我们就可以正难则反，我们假设先把所有的都选上，然后删去冲突的方案，删去最小的就相当于求最大的，最后建最小割模型就简单多了

最小费用最大流

为了解决更多的问题，边上多加一个权值 cost ，代表单位流量的花费，然后我们不仅要求出最大流，还要求出最大流状态下的最小总费用

首先，我们知道，在一条增广路上，整条增广路的流量由路径上残量最小的边决定，整条增广路的流量都是 min(flow) ，所以这条增广路的费用就是 sum(dis)*min(flow) 。

因为最大流的流量唯一，但方法不一定唯一，所以我们可以贪心一手，每次先处理出来最短路，在最短路上找增广路，一直增广到图不连通，这样我们找到的最大流一定是费用最小的。

这里注意反向边的处理，因为我们反向边是用来反悔的，走了反向边就相当于回退原边的流量，原边的费用肯定也要回退 (rnm，退钱) ，所以反向边的费用应该是 -cost

因为反边的存在，我们需要能处理负边权的最短路算法，于是SPFA又在网络流里活了，一般题SPFA都是能过的

所以我们把最大流的bfs换成SPFA就可以得到最小费用最大流的算法了，用SPFA+EK或SPFA+dinic都可以，这里注意dinic中的dfs要标记走过的点，不要在 cost=0 的边上转圈.

SPFA+EK 代码实现

#include<bits/stdc++.h>
using namespace std;

#define N 114514
#define M 1919810
#define inf INT_MAX
typedef long long ll;

namespace graph
{
    struct edge{
        int from, to, flow, cost, next;
    }side[M*2];
    int head[N], ccnt = 1;
    void insert(int from, int to, int flow, int cost)
    {
        side[++ccnt] = {from, to, flow, cost, head[from]}; head[from] = ccnt;
        side[++ccnt] = {to, from, 0, -cost, head[to]}; head[to] = ccnt;
    }

    int S, T;
    int pre[N];
    bool vis[N];
    ll dis[N];

    pair<ll,ll> EK();
    bool spfa(int S, int T);
}
using namespace graph;

int n, m;

signed main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        insert(u, v, w, c);
    }

    auto ans = EK();
    cout << ans.first << ' ' << ans.second;
}

pair<ll,ll> graph::EK()
{
    ll maxflow = 0, mincost = 0;
    while(spfa(S, T))
    {
        ll minf = LLONG_MAX;
        for(int x = T; x != S; x = side[pre[x]].from)
            minf = min(minf, (ll)side[pre[x]].flow);
        for(int x = T; x != S; x = side[pre[x]].from)
        {
            side[pre[x]].flow -= minf;
            side[pre[x]^1].flow += minf;
        }
        maxflow += minf;
        mincost += minf*dis[T];
    }
    return {maxflow, mincost};
}
bool graph::spfa(int S, int T)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; int x;
    q.push(S); dis[S] = 0;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        vis[x] = false;
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and dis[side[i].to] > dis[x]+side[i].cost)
            {
                dis[side[i].to] = dis[x]+side[i].cost;
                pre[side[i].to] = i;
                if(!vis[side[i].to])
                {
                    q.push(side[i].to);
                    vis[side[i].to] = true;
                }
            }
        }
    }
    return dis[T] != 0x3f3f3f3f3f3f3f3f;
}

SPFA+Dinic 代码实现

#include<bits/stdc++.h>
using namespace std;

#define N 114514
#define M 1919810
#define inf INT_MAX
typedef long long ll;

namespace graph
{
    struct edge{
        int to, flow, cost, next;
    }side[M*2];
    int head[N], ccnt = 1;
    void insert(int from, int to, int flow, int cost)
    {
        side[++ccnt] = {to, flow, cost, head[from]}; head[from] = ccnt;
        side[++ccnt] = {from, 0, -cost, head[to]}; head[to] = ccnt;
    }

    int S, T;
    bool vis[N];
    int cur[N];
    ll dis[N];

    pair<ll,ll> dinic();
    bool spfa(int S, int T);
    ll dfs(int x, ll flow);
}
using namespace graph;

int n, m;

signed main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        insert(u, v, w, c);
    }

    auto ans = dinic();
    cout << ans.first << ' ' << ans.second;
}

pair<ll,ll> graph::dinic()
{
    ll maxflow = 0, mincost = 0;
    while(spfa(S, T))
    {
        ll k = dfs(S, inf);
        maxflow += k;
        mincost += k*dis[T];
    }
    return {maxflow, mincost};
}
bool graph::spfa(int S, int T)
{
    memcpy(cur, head, sizeof(cur));
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; int x;
    q.push(S); dis[S] = 0;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        vis[x] = false;
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and dis[side[i].to] > dis[x]+side[i].cost)
            {
                dis[side[i].to] = dis[x]+side[i].cost;
                if(!vis[side[i].to])
                {
                    q.push(side[i].to);
                    vis[side[i].to] = true;
                }
            }
        }
    }
    return dis[T] != 0x3f3f3f3f3f3f3f3f;
}
ll graph::dfs(int x, ll flow)
{
    if(x == T) return flow;
    ll rest = flow, k; int i;
    vis[x] = true;
    for(i = cur[x]; i; i = side[i].next)
    {
        if(side[i].flow and !vis[side[i].to] and dis[side[i].to] == dis[x]+side[i].cost)
        {
            k = dfs(side[i].to, min(rest, (ll)side[i].flow));
            if(k == 0) dis[side[i].to] = LLONG_MAX;
            side[i].flow -= k;
            side[i^1].flow += k;
            if(!(rest -= k)) break;
        }
    }
    vis[x] = false;
    return cur[x] = i, flow-rest;
}

zkw费用流

上面的算法在每次SPFA处理出源点到其它点的最短路后进行增广，但是这样可能会进入一些根本不会到达汇点的分支，浪费很多时间，我们可以优化一下

想一个问题：给一个无向图，求S到T的所有路径并把路径都打上标记

这个问题我们可以分别从S和T进行bfs，被标记两次的边就一定是从S到T的路径上的边

我们可以按照这个思想来进行增广，所以我们从T向S跑最短路，然后从S向T增广流量，这样增广的边就一定是从S到T的路径上的边

这里注意从T到S跑SPFA时我们遍历到的边都是反边，需要通过i^1取出原来的正边的流量和费用，增广时判费用要用减法，具体可以看代码

#include<bits/stdc++.h>
using namespace std;

#define N 114514
#define M 1919810
#define inf INT_MAX
typedef long long ll;

namespace graph
{
    struct edge{
        int to, flow, cost, next;
    }side[M];
    int head[N], ccnt = 1;
    void insert(int from, int to, int flow, int cost)
    {
        side[++ccnt] = {to, flow, cost, head[from]}; head[from] = ccnt;
        side[++ccnt] = {from, 0, -cost, head[to]}; head[to] = ccnt;
    }

    int S, T;
    bool vis[N];
    int cur[N];
    ll dis[N];

    pair<ll,ll> dinic();
    bool spfa(int S, int T);
    ll dfs(int x, ll flow);
}
using namespace graph;

int n, m;

signed main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        insert(u, v, w, c);
    }

    auto ans = dinic();
    cout << ans.first << ' ' << ans.second;
}

pair<ll,ll> graph::dinic()
{
    ll flow = 0, cost = 0;
    while(spfa(S, T))
    {
        ll k = dfs(S, inf);
        flow += k;
        cost += k*dis[S];
    }
    return {flow, cost};
}
bool graph::spfa(int S, int T)
{
    memcpy(cur, head, sizeof(cur));
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; int x;
    q.push(T); dis[T] = 0;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        vis[x] = false;
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i^1].flow and dis[side[i].to] > dis[x]+side[i^1].cost)
            {
                dis[side[i].to] = dis[x]+side[i^1].cost;
                if(!vis[side[i].to])
                {
                    q.push(side[i].to);
                    vis[side[i].to] = true;
                }
            }
        }
    }
    return dis[S] != 0x3f3f3f3f3f3f3f3f;
}
ll graph::dfs(int x, ll flow)
{
    if(x == T) return flow;
    int rest = flow, k, i;
    vis[x] = true;
    for(i = cur[x]; i; i = side[i].next)
    {
        if(side[i].flow and !vis[side[i].to] and dis[side[i].to] == dis[x]-side[i].cost)
        {
            k = dfs(side[i].to, min(rest, side[i].flow));
            if(k == 0) dis[side[i].to] = 0x3f3f3f3f;
            side[i].flow -= k;
            side[i^1].flow += k;
            if(!(rest -= k)) break;
        }
    }
    vis[x] = false;
    return cur[x] = i, flow-rest;
}

Primal-Dual原始对偶

这个坑我先开了，以后再填(偷懒

#include<bits/stdc++.h>
using namespace std;

#define N 114514
#define M 1919810
#define INF 0x3f3f3f3f3f3f3f3f
#define pint pair<ll,int>
typedef long long ll;

namespace graph
{
    struct edge{
        int to;
        ll flow, cost;
        int next;
    }side[M];
    int head[N], ccnt = 1;
    void insert(int from, int to, ll flow, ll cost)
    {
        side[++ccnt] = {to, flow, cost, head[from]}; head[from] = ccnt;
        side[++ccnt] = {from, 0, -cost, head[to]}; head[to] = ccnt;
    }
    int S, T;
    bool vis[N];
    int pres[N], prex[N];
    ll dis[N], h[N];

    pair<ll,ll> MCMF();
    void spfa();
    bool dijkstra(int S, int T);
}
using namespace graph;

int n, m;

signed main()
{
    cin >> n >> m >> S >> T;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        insert(u, v, w, c);
    }

    auto ans = MCMF();
    cout << ans.first << ' ' << ans.second;
}

pair<ll,ll> graph::MCMF()
{
    ll flow = 0, cost = 0;
    spfa();
    while(dijkstra(S, T))
    {
        ll minf = INF;
        for(int i = 1; i <= n; i++)
            h[i] += dis[i];
        for(int x = T; x != S; x = prex[x])
            minf = min(minf, side[pres[x]].flow);
        for(int x = T; x != S; x = prex[x])
        {
            side[pres[x]].flow -= minf;
            side[pres[x]^1].flow += minf;
        }
        flow += minf;
        cost += h[T]*minf;
    }
    return {flow, cost};
}
void graph::spfa()
{
    memset(vis, 0, sizeof(vis));
    queue<int> q; int x;
    for(int i = 1; i <= n; i++)
        q.push(i);
    while(!q.empty())
    {
        x = q.front(); q.pop();
        vis[x] = false;
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and h[side[i].to] > h[x]+side[i].cost)
            {
                h[side[i].to] = h[x]+side[i].cost;
                if(!vis[side[i].to])
                {
                    q.push(side[i].to);
                    vis[side[i].to] = true;
                }
            }
        }
    }
}

struct node{
    int id; ll dis;
};
bool operator < (node a, node b)
{ return a.dis > b.dis; }

bool graph::dijkstra(int S, int T)
{
    std::priority_queue<node> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    q.push({S, 0}); dis[S] = 0;
    while(!q.empty())
    {
        int x = q.top().id; q.pop();
        if(vis[x]) continue; vis[x] = true;
        for(int i = head[x]; i; i = side[i].next)
        {
            if(side[i].flow and dis[side[i].to] > dis[x]+side[i].cost+h[x]-h[side[i].to])
            {
                dis[side[i].to] = dis[x]+side[i].cost+h[x]-h[side[i].to];
                q.push({side[i].to, dis[side[i].to]});
                pres[side[i].to] = i; prex[side[i].to] = x;
            }
        }
    }
    return dis[T] != INF;
}

有负环的费用流

咕咕咕~

二分图匹配

以网络流的特性来看，肯定能很容易地解决二分图匹配问题，因为限制流量就可以限制每个点的匹配数、被匹配数，多重匹配问题也随之解决

对于二分图带权最大匹配更简单了，直接权值取负数跑最小费用最大流，再对费用取反就可以直接解决二分图带权匹配问题

当然费用流对于二分图最大完美匹配的问题的处理速度还是不如KM算法的，但你可以通过极致卡常过掉 P6577

上下界网络流

无源汇上下界可行流

为了解决亿些更复杂的问题，光是有流量上限还不行，每个边的流量都有一个上界和下界，求是否存在一个流可以满足所有边的上下界和所有点流量平衡

首先这个下界很烦，有这个下界我们就很难套上面的板子，于是我们想办法把这个下界消掉

我们可以先满足所有边的下界，这样每条边就只剩下一个 r-l 的上界了，可以扔到普通网络流的板子里

但是这样又诞生了许多问题，首先满足下界之后势必会有一些点不满足流量平衡，一些点存了流量，一些点透支了流量，我们设每个点所存的流量为 val ，即流入量减去流出量

我们需要在满足上界的条件下，把存下的流量推送给透支的流量上，达到满足流量平衡

于是我们得想办法让一股流从多的点流到少的点，但我们又不能凭空造流，否则不满足流量平衡，于是我们需要建一个虚拟源点汇点，因为最大流中源点汇点可以不满足流量平衡

所以对于 val>0 的点，我们从 S 向它建一条流量为val的边，对于 val<0 的点，我们从它向 T 建一条流量为 -val 的边，然后跑最大流，这样我们所有存下的流量就可以流到透支的地方去了

设所有存下的流量为 sum ，即Σvali[vali>0]\Sigma val_i[val_i>0]，如果跑出来的流量等于 sum 的话，证明可以平衡掉所有的流量，即存在可行流，如果小于 sum 的话证明没有可行流

Code: 无源汇上下界可行流

有源汇上下界最大流

这个问题多了源汇，因为源汇是不需要满足流量平衡的，所以没法直接跑出可行流

以下部分用S和T代表虚拟源点汇点(跑网络流实际要用的)，s和t代表题目中实际的源点和汇点

这时候我们就可以从 t->s 建一条流量为 inf 的边，直接转化为无源汇问题，我们跑无源汇上下界可行流即可

但是直接跑的话可能没有达到最大流量，因为我们只满足了下界

但是我们已经满足下界了，就相当于没有了下界这个条件，这时再跑一次 s->t 的最大流，加到答案中，就是有源汇上下界最大流的答案了

因为跑出可行流之后已经满足了流量平衡，这时跑最大流除了 s 和 t 也是都满足流量平衡的，然后最大流会把能跑的流量全跑完，所以就可以求出答案来

这里要特别注意一定要删去之前建的 t->s 的边，否则就是一个死循环打到你脸上

Code: 有源汇上下界最大流

有源汇上下界最小流

其实跟上面差不多，最小流不就是尽量让流变小吗，我们可以先跑出可行流，然后从 t->s 跑一边最大流(感性理解)，减去跑出的流量，就是最小流的答案

就是从 t->s 能退回去多少就退回去多少流

有费用的上下界网络流

其实就是套个费用流，注意跑最小流的时候费用也是累加而不是减去第二部分的费用(退流时走的反边已经有退回费用的功能了)

例题

这里是我找的一些题，题单前半部分都是水题(锻炼敲板子和基础建模能力)，后半部分有一些稍微有难度的题，可以好好想一下

题单链接

经典的网络流24题，有些题还是很不错的

网络流24题

引用的一些资料

网络流建模