【学习笔记】网络流

Echoternity · 2022-11-18 18:02:58 · 个人记录

"或有一次天命陨落，但层出不穷，使万物若然。"

网络

网络流是网络中的流，网络是一张有向图，表示为 G=(V,E) ，对于每一条边 (u,v) ，存在一个权值 c(u,v) 表示容量 (capacity) ，当 (u,v)\notin E ，则有 c(u,v)=0 ，注意，不保证 c(u,v)=c(v,u) 。每一个网络有两个特殊点，一个是源点 (Source) s\in V ，一个是汇点(Sink) t\in V,(s\neq t) 。

流

一个实数函数满足 f(u,v),(u\in V,v\in E) ，且有：

• 容量限制 f(u,v)\leq c(u,v) ；
• 流守恒性 \sum^{i\in V,i\neq s}_{i}f(s,i)=\sum^{j\in V,j\neq t}_{j}f(j,t) ，即从源点流出的流量等于汇点流入的流量。
• 如果考虑反向边，则有第三性质：斜对称性 f(u,v)=-f(v,u) 。f 是 G 的流函数， f(u,v) 被称为 (u,v)\in E 的流量，而 f’(u,v)=c(u,v)-f(u,v) 称为边的剩余流量。则 \sum_{(s,v)\in E}f(s,v) 为从源点出发的流量和。

最大流

可以把网络流看作水库出水，而源点则是水库，汇点就是你家。源点的“量”是无限的，中途的任何一个点不存储任意一点流量也不会产生任何一点流量，所以源点出发的所有流量必定流入汇点。而经过每一条边的最大流量，即是 c(x,y)

最大流的算法，就是在满足流过边 c 的流量满足 \leq c(x,y) 的情况下，汇点的流量最大的问题。

残余网络

首先我们介绍一下一条边的剩余容量 c_f(u,v)（Residual Capacity），它表示的是这条边的容量与流量之差，即 c_f(u,v)=c(u,v)-f(u,v) 。

对于流函数 f ，残量网络 G_f（Residual Network）是网络 G 中所有结点 和剩余容量大于 0 的边构成的子图。形式化的定义，即 G_f=(V_f=V,E_f=\{(u,v)\in E,c_f(u,v)>0\}) 。

注意，剩余容量大于 0 的边可能不在原图 G 中（根据容量、剩余容量的定义以及流函数的斜对称性得到）。可以理解为，残量网络中包括了那些还剩了流量空间的边构成的图，也包括虚边（即反向边）。

以下是二月份初学时做下的笔记。

我们设 f(x,y) 为边 (x,y) 的实际容量。

• 饱和弧： f(x,y)=c(x,y) ，流量为该边的容量
• 非饱和弧： f(x,y)<c(x,y) ，实际流量小于容量
• 零流弧： f(x,y)=0 ，该边未流过流量。
• 非零流弧： f(x,y)>0 ，当前流量不为 0 。
• 残余网络：设有容量网络 G(V,E) 及其上的网络流 f ， G 关于 f 的残留网络即为 G(V’,E’) ，其中 G’ 的顶点集 V’ 和 G 的顶点集 V 相同，即 V’=V ，对于 G 中任何一条弧 (u,v) ，如果 f(u,v)<c(u,v) ，那么在 G’ 中有一条弧 (u,v)\in E’ ，其容量为 c’(u,v)=c(u,v)-f(u,v) ，如果 f(u,v)>0 ，则在 G’ 中有一条弧 (v,u)\in E’ ，其容量为 c’(v,u)=f(u,v) 。

从残留网络的定义来看，原容量网络中的每条弧在残留网络中都化为一条或者两条弧。在残留网络中，从源点到汇点的任意一条简单路径都对应一条增光路，路径上每条弧容量的最小值即为能够一次增广的最大流量。

增广路

增广路是一条从源点到汇点的路径，满足所有边的剩余容量都大于 0 ，则该路是网络 G 的一条增广路（Augmenting Path）。也可以定义为：残余网络 G_f 中，存在一条从源点到汇点的路径被称为增广路。

以下是二月份自学时做的笔记。

增广路是一条链。（链是网络中的一个顶点序列，这个序列中前后两个顶点有弧相连）链上的前向弧都是非饱和弧，链上的后向弧都是非零弧。（前向弧即输入的边，后向弧即建立的反边）链的起点是源点，终点是汇点。

增广路是一个边的集合，从 S 至 T 的一条路径。增广路的最大流量表示该路径经过的边中流量最小的边的流量，即：

一条增广路 i 的边集是 E_i ，最大流量是 c ，则 \forall r\in E,c_r\leq c 。

用赵悦岑巨佬的话来讲，增广路指的就是一条从源点到汇点，且经过的边最小容量不为 0 的路径。而我们寻找增广路之后，就会将所有经过的边的容量减去增广路的流量。但是，这种算法并不保险。所以我们对于每一条存在的 c(x,y) ，都建立其后向弧满足 c(y,x)=0 使得我们在后续寻找增广路时可以“反悔”，使其不因之前的错误增广路而影响。

我们对于每一条边都增加一条容量为 0 反向边，找到增广路后经过的边流量要减去此增广路的流量，其反向边的流量还要加上此增广路的流量。所有反向边组成的图就是残留网络。

反向边

增广时需要建造反向边，这是通理，虽然我也没有想明白其正确性。总之，增广的时候，由于贪心原则，其并非全局最优解，而减去之后会导致最优解无法到达，我们要让子程序进行反悔。那么，我们每次增广的时候，就要建造一个反向边满足 c(v,u)=f(u,v) ，即反向边的容量是正向边的流量。我无法解释为什么，反正它确实对了。

对于建反向边的技巧，邻接矩阵就是 table[x,y]=table[y,x] 。而链式前向星更常用，我们也不需要在增广时才加入反向边，我们可以预处理出反向边，而在用的时候直接将 id\operatorname{xor}1 即可。这个不必太多解释。但是，初始值需要有 Total=-1 或者 Total=1 ，如果边从 1 开始，则会错位。

Edmonds-Karp 动能算法

圈内人称 \text{EK} 算法。

算法只有一句话，用 \text{bfs} 找增广路，然后对其进行增广即可。

• 找：从源点开始 \text{bfs} ，直到碰到汇点，然后进行增广（每一条路），注意流量合法。
• 增广：重走找到的增广路，然后减去这条路能够达到的最大流量，然后把答案加上最小流量即可。时间复杂度 \mathcal O(nm^2) ，不太效率。但是好想和好记。

时间复杂度 \mathcal O(nm^2) ，不太效率，但是比较好想也比较好记。

const int MAXN=201,MAXM=5001;
const int INF=0x7f7f7f7f;
namespace EdmondsKarp
{
    int Total;
    vector<Edge>Edges;
    vector<int>G[MAXN];
    int fl[MAXN],id[MAXN];
    inline void init()
    {
        for(int i=1;i<=N;++i) G[i].clear();
        Edges.clear();
    }
    inline void addEdge(int u,int v,int c)
    {
        Edges.push_back(Edge(u,v,c,0));
        Edges.push_back(Edge(v,u,0,0));
        Total=Edges.size();
        G[u].push_back(Total-2);
        G[v].push_back(Total-1);
    }
    inline ll maxFlow(int s,int t)
    {
        ll flow=0;
        for(;;)
        {
            memset(fl,0,sizeof(fl));
            queue<int>Q;
            Q.push(s);
            fl[s]=INF;
            while(!Q.empty())
            {
                int u=Q.front();Q.pop();
                for(int i=0;i<G[u].size();++i)
                {
                    Edge& e=Edges[G[u][i]];
                    if(!fl[e.to]&&e.cap>e.flow)
                    {
                        id[e.to]=G[u][i];
                        fl[e.to]=min(fl[u],e.cap-e.flow);
                        Q.push(e.to);
                    }
                }
                if(fl[t]) break;
            }
            if(!fl[t]) break;
            for(int u=t;u!=s;u=Edges[id[u]].from)
            {
                Edges[id[u]].flow+=fl[t];
                Edges[id[u]^1].flow-=fl[t];
            }
            flow+=fl[t];
        }
        return flow;
    }
};
using namespace EdmondsKarp;
int main()
{
    // freopen("ek.in","r",stdin);
    // freopen("ek.out","w",stdout);
    read(N,M,S,T);
    EdmondsKarp::init();
    for(int i=1,u,v,c;i<=M;++i)
    {
        read(u,v,c);
        EdmondsKarp::addEdge(u,v,c);
    }
    printf("%lld",EdmondsKarp::maxFlow(S,T));
    return 0;
}

Dinic

在学习完 \text{EK} 之后，我才真正开始理解 \text{Dinic} 的本质。

思路同 \text{EK} ，但是在增广之前，使用 bfs 进行分层（将图进行分层处理，建图的常见技巧之一），源点的层数满足 dep[s]=0 ，其他点的层数取决于其与源点的距离。

分层之后，有两个优化：

同时进行多路增广，且在断层时（即找不到增广路的时候）直接中断增广，进行时间优化；增广路一定最短。我们用 dfs 来找增广路。对层数加 1 的点进行增广（从而确保增广路最短，原理同最短路，因为同层的点只会经过一个）。

Dinic 的优化

• 多路增广：每找到一条增广路之后，从残余流量再次增广；从而在一次 dfs 中找出多条增广路，提高算法效率。
• 当前弧优化：可以推出（或者直接背下），一条边如果已经是一条增广路的边（被增广过），那么这条边不可能被增广第二次。所以，对所有边进行标记，不必要再走已经被增广过的边。

在运用了上述两个优化之后，时间复杂度可以达到 \mathcal O(n^2m) ，在稠密图上比 EK 更胜一筹。就和 SPFA 一样，这个上界一般而言很难到达，且在二分图最大匹配问题上，Dinic 算法的复杂度能达到 \mathcal O(m\sqrt n) ，不过不在我今天讲的范围内，所以只是提一嘴。

以下讲解不太明晰（个人意见），酌情观看。

• 每次多路增广： u 点通过一条边，向 v 输出流量以后， v 会尝试到达汇点（到达汇点才真正增广），然后 v 返回实际增广量。这时，如果 u 还有没用完的供给，就继续尝试输出到其它边。
• 但是要警惕绕远路、甚至绕回的情况，不加管制的话极易发生。怎么管？
• 源点顺着残量网络想要到达其它点，需要经过一些边对吧？按照经过的边数（即源点出发以后的距离）把图分层，即用 bfs 分层。 每次尝试给予时，只考虑给予自己下一层的点，就可以防止混乱。
• 综合上面两条。每回合也是从源点出发，先按照当前残量网络分一次层，随后多路增广，尽可能增加流量。增广过程中，会加入一些反向边，这些反向边逆着层次图，本回合并不会走。所以还需要进入下一回合。一直到 bfs 分层时搜不到汇点（即残量网络断了）为止。

对于任意一个可行流 f(s,t) 的割 (S,T) ，则有：

那么，令 f 是最大流，则其残余网络中不会存在 (s,t) 的增广路，那么 S 的出边是满流，入边是零流，则：

而此时的 f(s,t) 实际上是流函数 f 的 f(s,t)_{\max} 。

求割边数量

即在满足最小割的前提下，最小化割边的数量（即删除的边的数量）。首先跑最大流求出最小割，然后将没有满流的边容量改成 inf ，并将满流了的边的容量改为 1 ，重新跑一遍最小割，求出来的即是最小割边数。如果没有最小割，则直接将所有边的容量都设为 1 并跑最小割。

另外两种方法可以参考这一篇题解。

全局最小割 x Stoer-Wagner 算法

你可以把它理解为无源汇最小割，其最小割的重定义为：

去掉其中一些边能使一张网络不再连通的边集称为该网络的割。

其最小割定义为方案中边集和最小的一种方案。

使用 \text{Stoer-Wagner} 算法来解决这个问题。（因为无源汇，所以你暴力建源汇点跑 N^2 次即使是 ISAP 也是行不通的）

时间复杂度 \mathcal O(|V||E|+|V|^2\log |V|) 近似于 \mathcal O(V^3) 。

存在一个结论：

图中有任意两点 u,v ，存在 G 的任意一个割 C ，要么 u 和 v 连通，在同意连通块；要么 C 是一个 u-v 割。

边数：|E|=2(N+3M)

const int MAXN=5e3+10;
const int MAXM=5e4+10;
const ll INF=1145141919810;
int N,M,S,T;
struct Net
{
    int next,to;ll val;
}Edge[2*MAXN+6*MAXM];
int Head[MAXN+MAXM],Cur[MAXN+MAXM],Total=1;
inline void addEdge(int u,int v,ll w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXN+MAXM];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[S]=0,Cur[S]=Head[S];
    std::queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
ll Dfs(int x,ll inf)
{
    if(x==T) return inf;
    ll flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        v=Edge[e].to,Cur[x]=e;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            ll k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline ll Dinic()
{
    ll r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
ll sum;
int main()
{
    // freopen("mincut.in","r",stdin);
    // freopen("mincut.out","w",stdout);
    read(N,M);
    S=0,T=N+M+1;
    for(int i=1;i<=N;++i)
    {
        ll w;read(w);
        addEdge(i+M,T,w);
    }
    for(int i=1,u,v;i<=M;++i)
    {
        ll w;read(u,v,w);sum+=w;
        addEdge(i,u+M,INF);
        addEdge(i,v+M,INF);
        addEdge(S,i,w);
    }
    write(sum-Dinic());
    return 0;
}

最大密度子图

对于一个图 G=(V,E) ，选出其一个子边集 E'\subseteq E ，在求出一个子点集 V'\subseteq V,\forall u,v\in V',(u,v)\in E' ，即 E' 集合中所有的边的两端点都必须在 V' 中。对于一个子图 G'=(V',E') 满足 \frac{\mid E'|}{|V'|} 最大，则 G' 是 G 的最大密度子图。

这让人不禁想到了 01 规划 ，所以也就采用二分求解。但是判断函数需要联系到最小割去。

再次回忆一次 01 规划的思路。

令 \frac{|E'|}{|V'|}=g ，则有 |E'|=g|V'| ，那么如果要让该式子最大，则有 \frac{|E'|}{|V'|}>g ，同理就有 |E'|-g|V'|>0 ，那么问题就可以转化为求出 |E'|-g|V'| 的最大值，或者求 g|V'|-|E'| 的最小值。

有一种方法是把求最大密度子图转化为最大权闭合图来做。但这样时间复杂度较高。

点数： |V|+|E| ，边数 3|E|+|V| 。

从最大密度子图的定义来看，它是满足了闭合图的性质的。而由边定点，对于边 e=c(u,v) ，我们可以看做有一个点 e ，有边 u 和边 v 与其相连。

建图：

1. 从超级源点 S 到所有边点 e 链接一条容量为 1 的边；
2. 从已知点 e_a 到已知点 e_b 链接一条容量为 inf 的边；
3. 从所有边点 e 到超级汇点 T 链接一条容量为 g 的边。（g 是当前二分抉择）

然后跑最小割以求最大权闭合子图，求出的最大权就是 |E'|-g|V'| 的最大值。

性质法

已知算式 |E'|-g|V'| 与 g|V'|-|E'| 一一对应，且当 |E'|-g|V'| 最大时，g|V'|-|E'| 正好取得最小值，我们可以从这一方面入手。

选择的点集为 |V'| 的话，则点集内所有的边都被选择的情况，是对于当前点集最优的情况。

该性质显然，无需证明。

我们定义一个反点集 \overline{V'}=V-V' ，即所有没有选择的点的集合，并定义一个函数 deg[v] 表示 v 的度数。（即有多少条边以 v 为端点）

有：

设集合内部所有点的度数之和是 sum ，那么，处于集合内部的边一定被计算了 2 次，因为该边的两个端点均在集合内。而处于集合 V' 与集合 \overline{V'} 之间的割边只被计算了一次，而这样的割边的数量就是该割的容量 C(V',\overline{V'}) ，因为原图的所有边的容量在流网络中都设置成了 1 。

变换形式，得到一个较好处理的式子：

在每一次抉择时， 2g-dep[v] 的值是相等的，所以影响整个式子的唯一点就是这张图的最小割。

再说说怎么建图：（讲的不是太明白）

1. 从每一个点往超级汇点 T 链接一条容量为 2g-deg[v]+Q 的边；
2. 从超级源点 S 向每一个点链接一条容量为 Q 的边。
3. 取出原图，将所有原边的容量修改为 1 。

这里的 Q 是一个常数，一个偏移量，一个满足 2g-dep[v] 是正数的任意值，一般可以取到 |E| ，即原图的边数。（Q 存在的原因是容量不能为负）

我们已知，割的容量 C(S,T) 表达式可以有三种：

1. s\rightarrow \overline{V'}
2. V'\rightarrow t
3. V'\rightarrow \overline{V'}

其中 V'=S-s 。

以 c_{(u,v)} 的一个 \{0,1\} 函数表示 u,v 之间是否连接，则有

因为有：

而 $\sum_{v\in\overline{V'}}c_{(u,v)}$ 表示的是点 $u$ 到达集合 $V'$ 外部 $\overline{V'}$ 的边数； 相减得到点 $u$ 到达集合内部的边数 $\sum_{u\in V'}c_{(u,v)}

再次化简：

最后得到一个肥肠简单的式子：

显然地，nQ 是针对全局的定值，而 \min\{g|V'|-|E'|\} 就是整道题的答案，也就有：

总结全题：

点数：|V| ，边数：2|V|+|E| 。时间复杂度在于 \mathcal O(\log (l,r)\times \mathcal O(maxFlow)) ，取决于二分的值域以及跑最小割（最大流）的算法。

后来发现，二分的值域可以取 [\frac{1}{n},m] ，不过取 [0,m] 也不会有太大影响。

需要注意的是：上述所有方法都是限于无权点无权边最大密度子图问题，如果有权点或者有权边则需另加讨论。

模板题指路

const int MAXN=201,MAXM=5e3+1;
const int INF=1e9;
const double eps=1e-8;
int N,M,S,T;
struct G
{
    int next,to;
    double val;
    G(int n=0,int t=0,double v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
struct Eg
{
    int u,v;
}Edges[MAXM<<1];
int Head[MAXN],Total=1;
int Deg[MAXN],ans,Cur[MAXN];
bool St[MAXN];
inline void addEdge(int u,int v,double w1,double w2)
{
    Edge[++Total]=G(Head[u],v,w1);Head[u]=Total;
    Edge[++Total]=G(Head[v],u,w2);Head[v]=Total;
}
void build(double g)
{
    memset(Head,0,sizeof(Head));
    Total=1;
    for(int i=1;i<=M;++i) addEdge(Edges[i].u,Edges[i].v,1,1);
    for(int i=1;i<=N;++i)
    {
        addEdge(S,i,M,0);
        addEdge(i,T,M+g*2-Deg[i],0);
    }
}
int Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[S]=0,Cur[S]=Head[S];
    queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val>0)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
double Dfs(int x,double inf)
{
    if(x==T) return inf;
    double flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val>0)
        {
            double k=Dfs(v,min(Edge[e].val,inf-flow));
            if(k<=0) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
double Dinic(double g)
{
    build(g);
    double r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
void Search(int x)
{
    St[x]=1;
    if(x!=S) ++ans;
    for(int e=Head[x];e;e=Edge[e].next)
    {
        int v=Edge[e].to;
        if(!St[v]&&Edge[e].val>0) Search(v);
    }
}
int main()
{
    // freopen("minCut.in","r",stdin);
    // freopen("minCut.out","w",stdout);
    while((scanf("%d%d",&N,&M))!=EOF)
    {
        S=0,T=N+1;
        memset(Deg,0,sizeof(Deg));
        memset(St,0,sizeof(St));
        ans=0;
        for(int i=1,u,v;i<=M;++i)
        {
            read(u,v);
            ++Deg[u],++Deg[v];
            Edges[i]={u,v};
        }
        double l=0,r=M;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            double k=Dinic(mid);
            if(M*N-k>0) l=mid;
            else r=mid;
        }
        Dinic(l);
        Search(S);
        if(!ans) printf("1\n1\n");
        else
        {    
            printf("%d\n",ans);
            for(int i=1;i<=N;++i)
                if(St[i]) printf("%d\n",i);
        }
    }
    return 0;
}

最小权点覆盖集

点覆盖集 A 是一个集合，满足图上所有边的至少一个端点都在集合内，所有点覆盖集中，总点权值最小的集合就是最小权点覆盖集。

求解是一个 \text{NP} 完全问题。即没有多项式时间复杂度的做法，有且仅有枚举暴力的实现。但在一个二分图里，有一种特殊的最小权点覆盖集。

最大权独立集

对于一般的最大权独立集而言，指的是：

在一个图 G 中选取一个点集 A ，使 A 中任意两点不相连，其中 |A| 最大的集合称为 G 的最大权独立集。

网络最大流解决二分匹配问题

二分图最大匹配（网络流算法）

构造网络流模型：

1. 建立一个超级源点 S 与 n 中所有结点链接一条容量为 1 的边，表示一个结点只能被用 1 次；
2. 建立一个超级汇点 T 与 m 中所有结点链接一条容量为 1 的边，表示一个结点只能匹配 1 次。
3. 对于原图，链接 n 中的 u 与 m 中的 v ，容量为 1 。

求出该图的最大流即是该二分图的最大匹配。

const int MAXP=2001,MAXE=1e5+1;
const int INF=0x7f7f7f7f;int N,M,E,S,T;
struct G
{
    int next,to,val;
    G(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXE<<1];
int Head[MAXP],Cur[MAXP],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=G(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=G(Head[v],u,0);Head[v]=Total;
}
int Fl[MAXP];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[S]=0,Cur[S]=Head[S];
    queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("Dinic.in","r",stdin);
    // freopen("Dinic.out","w",stdout);
    read(N,M,E);
    S=0,T=N+M+1;
    for(int i=1,u,v;i<=E;++i)
    {
        read(u,v);
        addEdge(u,M+v,1);
    }
    for(int i=1;i<=N;++i) addEdge(S,i,1);
    for(int i=1;i<=M;++i) addEdge(i+M,T,1);
    printf("%d",Dinic());
    return 0;
}

网络流解决二分匹配

以飞行员配对方案问题为例，最重要的是建出网络模型，然后照板子跑就好了。建出一个 S 源点和一个 T 汇点，然后链接 S 和所有外籍飞行员，链接 T 和所有英国飞行员，然后将所有能够匹配的外籍飞行员和英国飞行员链接，容量皆为 1 。最后检验一些建构出的网络的可行流和原问题的可行方案是否对应，如果是，说明建图成功，跑模板。

const int MAXN=101;
const int INF=0x7f7f7f7f;
int N,M,S,T;
struct Graph
{
    int next,to,val;
    Graph(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXN*MAXN];
int Head[MAXN],Total=1,newTail[MAXN],Fl[MAXN];
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
inline bool Bfs()
{
    queue<int>Q;
    memset(Fl,0,sizeof(Fl));
    Fl[S]=1;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u];e;e=Edge[e].next)
            if(!Fl[Edge[e].to]&&Edge[e].val)
            {
                Fl[Edge[e].to]=Fl[u]+1;
                Q.push(Edge[e].to);
            }
    }
    return Fl[T]!=0;
}
inline int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int s=0;
    for(int e=newTail[x];e;e=Edge[e].next)
    {
        newTail[x]=e;
        if(Fl[Edge[e].to]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(Edge[e].to,min(inf-s,Edge[e].val));
            if(k)
            {
                Edge[e].val-=k;
                Edge[e^1].val+=k;
                s+=k;
            }
        }
    }
    if(s<inf) Fl[x]=-1;
    return s;
}
inline void Dinic()
{
    int maxFlow=0;
    while(Bfs())
    {
        for(int i=0;i<=N+1;++i) newTail[i]=Head[i];
        maxFlow+=Dfs(S,INF);
    }
    if(maxFlow==0) printf("No Solution!");
    else
    {
        printf("%d\n",maxFlow);
        for(int i=2;i<=Total;i+=2)
        {
            if(Edge[i].to!=S&&Edge[i^1].to!=S)
                if(Edge[i].to!=T&&Edge[i^1].to!=T)
                    if(Edge[i^1].val!=0)
                        printf("%d %d\n",Edge[i^1].to,Edge[i].to);
        }
    }
}
int main()
{
    // freopen("dinic.in","r",stdin);
    // freopen("dinic.out","w",stdout);
    read(M,N);
    int u,v;
    T=N+1;
    read(u,v);
    while(u!=-1&&v!=-1)
    {
        addEdge(u,v,1);
        read(u,v);
    }
    for(int i=1;i<=M;++i) addEdge(S,i,1);
    for(int i=M+1;i<=N;++i) addEdge(i,T,1);
    Dinic();
    return 0;
}

最小割求解最小权点覆盖集

有性质：

在二分图中，有一个特殊的性质：当所有点权都是 1 时，有最大匹配数等于最小权点覆盖集；最大权独立集等于点数减去最小权点覆盖集。

在二分图中，最小权点覆盖集解决了这一类问题：

在二分图中，对于每条边，两个端点至少选一个，求所选取的点的最小权值和。

对应方法：

1. 二分图染色，使每一条边的端点颜色不同；
2. 建立超级源点 S 与所有颜色为 a 的边链接一条容量为该点权值的边；
3. 建立超级汇点 T 与所有颜色为 b 的边链接一条容量为该点权值的边。
4. 对于二分图中原有的边，改为从 u 到 v 的容量为 inf 的边。

求取构造网络的最大流（最小割），结果则是最小点权和。 （这个结论我暂时还没有理解，但是挺好背，所以先背比较好）

最小割求解最大点权独立集

因为有：

最大权独立集等于所有点的总权值减去最小权点覆盖。

所以这两个问题其实是相通的，只是输出的答案略微不同罢了。

最大点权独立集模板题的双倍经验。

因为不能够选相邻的点，则我们将所有点分为两类使每一类不存在相邻。

建图：

1. 对于所有 a 类点，链接 (S,a,pt[a]) ；

2. 对于所有 b 类点，链接 (b,T,pt[b]) ；

3. 对于相邻的点 u,v ，链接 (u,v,inf) 。

如上述方法一致。

const int MAXN=101,MAXP=2e4+1,MAXE=2e6+1;
const int INF=0x3f3f3f3f;
const int Dx[]={0,1,-1,0,0};
const int Dy[]={0,0,0,-1,1};int N,M,S,T;
struct G
{
    int next,to,val;
    G(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXE<<1];
int Head[MAXP],Cur[MAXP],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=G(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=G(Head[v],u,0);Head[v]=Total;
}
int Fl[MAXP];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[S]=0,Cur[S]=Head[S];
    queue<int>Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
bool Color[MAXN][MAXN];
int main()
{
    // freopen("netflow.in","r",stdin);
    // freopen("netflow.out","w",stdout);
    read(N,M);
    S=0,T=N*M+1;
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
        {
            if(((i&1)&&(j&1))||((!(i&1))&&(!(j&1))))
                Color[i][j]=1;
            else Color[i][j]=0;
        }
    /*for(int i=1;i<=N;++i){
        for(int j=1;j<=M;++j) cout<<Color[i][j]<<" ";
        puts("");
    }*/
    ll Cnt=0;
    for(int i=1;i<=N;++i)
        for(int j=1,x;j<=M;++j)
        {
            read(x);
            Cnt+=x;
            if(Color[i][j]) addEdge(M*(i-1)+j,T,x);
            else
            {
                addEdge(S,M*(i-1)+j,x);
                for(int k=1;k<=4;++k)
                {
                    int Nx=i+Dx[k],Ny=j+Dy[k];
                    if(Nx<1||Ny<1||Nx>N||Ny>M) continue;
                    addEdge(M*(i-1)+j,M*(Nx-1)+Ny,INF);
                }
            }
        }
    printf("%d",Cnt-Dinic());
    return 0;
}

上下界网络流

字面意思，对于每一条边的可行流，存在最小流 min(c(u,v)) 和最大流 max(c(u,v)) ，该边在满足最大流的所有性质的前提下，必须满足 min(c(u,v))\le f(c(u,v))\le max(c(u,v)) 。这是上下界可行流。

上下界流分为有源汇和无源汇两种情况。

无源汇上下界可行流

所谓可行流，就是满足容量限制，流守恒性，斜对称性的流。而对于拥有上下界的网络，其限制严格许多。

首先，下界必须流满，所以我们可以在建边时直接将容量建为 upper(x)-lower(x) ，但是又考虑到每条边的下界并不一定相等，所以，我们需要额外找出位置来平衡流量：

建立虚拟源点和虚拟汇点。

令虚拟源点为 vS ，虚拟汇点为 vT ，对于点 x 流入的流量为 in_x ，流出的流量为 out_x 。出入的流量差记为 dif[x],dif[x]=in_x-out_x 。则有：

这样其实就变成了一个常规的有源汇网络，然后跑最大流即可（毕竟最大流也是一种特殊的可行流）。如果跑得出来，那么除了 vS 和 vT 之外的所有点的容量应当是守恒的，则说明原图存在可行流。

模板无源汇上下界可行流

const int MAXN=501,MAXM=2e5+1;
const int INF=0x7f7f7f7f;
int N,M,vS,vT;
struct Graph
{
    int next,to,val;
    Graph(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Lo[MAXM<<1],Total=1;
inline void addEdge(int u,int v,int lo,int up)
{
    Edge[++Total]=Graph(Head[u],v,up-lo);Lo[Total]=lo;Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
int Fl[MAXN],Dif[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[vS]=0,Cur[vS]=Head[vS];
    queue<int>Q;
    Q.push(vS);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==vT) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==vT) return inf;
    int flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(vS,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("unset-flow.in","r",stdin);
    // freopen("unset-flow.out","w",stdout);
    read(N,M);
    vS=0,vT=N+1;
    for(int i=1,u,v,lo,up;i<=M;++i)
    {
        read(u,v,lo,up);
        addEdge(u,v,lo,up);
        Dif[u]-=lo,Dif[v]+=lo;
    }
    int Tot=0;
    for(int i=1;i<=N;++i)
        if(Dif[i]>0) addEdge(vS,i,0,Dif[i]),Tot+=Dif[i];
        else if(Dif[i]<0) addEdge(i,vT,0,-Dif[i]);
    if(Dinic()!=Tot) printf("NO");
    else
    {
        puts("YES");
        for(int e=2;e<=M*2;e+=2)
            printf("%d\n",Edge[e^1].val+Lo[e]);
    }
    // for(int e=1;e<=M*2;++e) printf("%d ",Lo[e]);
    return 0;
}

有源汇上下界可行流

有给定的源点和汇点，求该网络的可行流。

凡事讲究一个推进，所以我们选择将有源汇的问题转化为无源汇的问题。首先，对于有源汇的问题而言，其与无源汇问题最大的不同就在于其 S 源点的流量与 T 汇点的流量一定不同。那么，我们就需要使其相同：

连接一条从 T 到 S 上界为 inf 下界为 0 的边。这样就会使流量守恒定律一样满足于源汇点了。

有源汇上下界最小/最大流

最大流

首先跑出一条可行流，对于虚拟源点 vS 到虚拟汇点 vT 的边已经流满，但是通过定义：最大流 = 可行流 + 向上浮动的流量。所以我们要在残余网络中尽量跑满上限。

而我们需要在原图的源汇路径上重找增广路，可以得到结论是向上浮动的流量就是真实源点 S 到真实汇点 T 的最大流。

注意：跑最后一次最大流时需要把边 (T,S,inf) 删掉。

模板有源汇上下界最大流

const int MAXN=501,MAXM=2e4+1;
const int INF=0x7f7f7f7f;
int N,M,S,T,Sv,Tv;
struct Graph
{
    int next,to,val;
    Graph(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
int A[MAXN],Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[Sv]=0,Cur[Sv]=Head[Sv];
    queue<int>Q;
    Q.push(Sv);
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int e=Head[x];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[x]+1;
                Cur[v]=Head[v];
                if(v==Tv) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==Tv) return inf;
    int flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(Sv,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("maxflow.in","r",stdin);
    // freopen("maxflow.out","w",stdout);
    read(N,M,S,T);
    Sv=0,Tv=N+1;
    for(int i=1,u,v,w,c;i<=M;++i)
    {
        read(u,v,w,c);
        addEdge(u,v,c-w);
        A[u]-=w,A[v]+=w;
    }
    int Tot=0;
    for(int i=1;i<=N;++i)
        if(A[i]>0) addEdge(Sv,i,A[i]),Tot+=A[i];
        else if(A[i]<0) addEdge(i,Tv,-A[i]);
    addEdge(T,S,INF);
    if(Dinic()<Tot) puts("please go home to sleep");
    else
    {
        int res=Edge[Total].val;
        Sv=S,Tv=T;
        Edge[Total].val=Edge[Total-1].val=0;
        printf("%d\n",res+Dinic());
    }
    return 0;
}

最小流

从代码的角度来讲，最小流代码与最大流代码只有 2 处不同。

把上下界最大流比作是“榨干”，那上下界最小流就是把残余网络“退钱”。——\text{yxc}

所以，最后从 T 向 S 跑一遍最大流，再把第一次跑的最大流减去跑的第二次最大流就是原图的最小流了。

也要删去最后一条边！！

模板有源汇上下界最小流

const int MAXN=1e5+1,MAXM=3e5+1;
const int INF=0x7f7f7f7f;
int N,M,S,T,vS,vT;
struct Graph
{
    int next,to,val;
    Graph(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
int Fl[MAXN],A[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    Fl[vS]=0,Cur[vS]=Head[vS];
    queue<int>Q;
    Q.push(vS);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==vT) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==vT) return inf;
    int flow=0;
    for(int e=Cur[x];e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e;
        int v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(vS,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("minflow.in","r",stdin);
    // freopen("minflow.out","w",stdout);
    read(N,M,S,T);
    vS=0,vT=N+1;
    for(int i=1,u,v,up,lo;i<=M;++i)
    {
        read(u,v,lo,up);
        addEdge(u,v,up-lo);
        A[u]-=lo,A[v]+=lo;
    }
    int Tot=0;
    for(int i=1;i<=N;++i)
        if(A[i]>0) addEdge(vS,i,A[i]),Tot+=A[i];
        else if(A[i]<0) addEdge(i,vT,-A[i]);
    addEdge(T,S,INF);
    if(Dinic()<Tot) printf("please go home to sleep");
    else
    {
        int res=Edge[Total].val;
        vS=T,vT=S;                      //不同点1
        Edge[Total].val=Edge[Total-1].val=0;
        printf("%d",res-Dinic());       //不同点2
    }
    return 0;
}

费用流

最小费用最大流

不同于最大流的普通网络，对于每一条边，除了源初的 c(u,v) 表示容量限制以外，还存在一个单位流量的费用表示 w(u,v) 。即流过 1 个单位流量所花费的费用。

则有当边 (u,v) 流过 f(u,v) 的流量时，就需要支付 f(u,v)\times w(u,v) 的费用。