网络流

在这个大家都在 P 的时代里，是时候拿出点真的 P 话了。

MCMF

P3381 【模板】最小费用最大流

先看题，相信大家都不知道啥意思，谁不是呢，其实就是有张有向图，有个容量（最多留多少流量），有个单位费用（留1流量要花这些单位费用），有个源点 $s$ 来无限的流水，然后有个 $t$ 来收水，我们要做 $2$ 件事，就是求最大流，也就是从 $s$ 到 $t$ 的最长路？你可以这样理解，但是其实是最多能流过多少流量。

第二件事就是在流量等于这个值时求出最小的花费。

其实就是用最少的钱流最多的水。

这里区分下最大流与最小费用最大流，最大流就是好比你是野兽先生，你不用管花多少钱，只要最大就行，但后者要节约花钱（求最小费用）。

这里提一句，网络流代码可以自动建反向边，所以不用管这个点。

看代码吧。

#include <iostream>
#include <queue>
#include <cstring>
using namespace syh;
typedef long long ll;
const int maxn=5*1e3+5;
const int maxm=1e5+5;//这里是*2的意思，因为有反向边也要建
const ll INF=1e18;
struct edge//链式前向星
{
    int to, nex;//to 目标点，nex 同起点下一条边的编号
    ll cap, cos;//cap 剩余容量，cos 单位费用
}e[maxm];
int head[maxn], tot;//tot为边计数器，head[u]为u点的第一条边编号
ll dis[maxn];//最短路数组
bool inq[maxn];//SPFA标记
int pre[maxn];//到达v点的边的编号，用于回溯增广路
void add(int u,int v,ll cap,ll cos)//建边（自动建反向边）
{
    e[++tot]={v,head[u],cap,cos};
    head[u]=tot;
    e[++tot]={u,head[v],0,-cos};//反向边费用取反，容量0，用于退流
    head[v]=tot;
}
pair<ll,ll> MCMF(int s,int t)//MCMF是最小费用最大流的意思，返回的是总流量与总费用
{
    ll flo=0, cos=0;//flo 最大流量，cos 费用之和
    while(1)//跑最短路
    {
        fill(dis,dis+maxn,INF);
        memset(inq,0,sizeof inq);
        queue<int> q;
        dis[s]=0;
        q.push(s);
        inq[s]=1;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            inq[u]=0;
            for(int i = head[u];i;i=e[i].nex)//遍历邻边
            {
                int v=e[i].to;
                if(e[i].cap>0&&dis[v]>dis[u]+e[i].cos)//有剩余的容量且可以更新最小费用
                {
                    dis[v]=dis[u]+e[i].cos;
                    pre[v]=i;//记录前驱边
                    if(!inq[v]) 
                    {
                        q.push(v);
                        inq[v]=1;
                    }
                }
            }
        }
        if(dis[t]==INF) break;//不可达就结束
        ll f=INF;//找增广路上最大的流量
        for(int v=t;v!=s;v=e[pre[v]^1].to)
        {
            f=min(f,e[pre[v]].cap);
        }
        flo+=f;//加进总流量
        cos+=dis[t]*f;//总费用为流量*单位费用
        for(int v=t;v!=s;v=e[pre[v]^1].to)//更新下残量网络
        {
            e[pre[v]].cap-=f;//正向边的这个流量流走了
            e[pre[v]^1].cap+=f;//这条反向边可以反悔退流
        }
    }
    return {flo,cos};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin>>n>>m>>s>>t;
    tot=1;
    for(int i = 1;i<=m;i++)
    {
        int u, v;
        ll w, f;
        cin>>u>>v>>w>>f;
        add(u,v,w,f);//建图
    }
    auto [x,y]=MCMF(s,t);
    cout<<x<<" "<<y;
}

P4014 分配问题

$n$ 人做 $n$ 份工作，一人一份，一份一人，求最小/最大总效益。

哇这就是题意吗？

让我们拿个二分图出来，左边放人，右边放工作，建虚拟源点 $s$ 和虚拟汇点 $t$ ，建边规则是：

1. $s$ 到人 每人一份。
2. 人到工作 名额消耗 $1$ ，效益加 $c_{ij}$。
3. 工作到 $t$ 一人一份。

这个图的最大流一定为 $n$ ，那么最小的费用就是最小的总效益，那最大的咋求？把边取负数跑最小费用流最后答案取负的就可以了。

为啥可以这样？

因为从 $s$ 流到 $t$ 就是在分配工作，那么流到了就证明所有的工作都被分配完了，这就是二分图能完美匹配的原因（$s$ 最多流 $n$），而且我们的 MCMF 会自动选出费用最少的匹配方案。

所以我们第一次建图时跑 MCMF 求出最小费用，然后清图再建 $-c_{ij}$ 的图跑最小费用流就有了最大费用。

#include <iostream>
#include <queue>
#include <cstring>
using namespace syh;
typedef long long ll;
const int maxn=115;
const int maxm=1e4+5;
const ll INF=1e18;
struct edge
{
    int to, nex;
    ll cap, cos;
}e[maxm];
int head[maxn], tot;
ll dis[maxn];
bool inq[maxn];
int pre[maxn];
void add(int u,int v,ll cap,ll cos)
{
    e[++tot]={v,head[u],cap,cos};
    head[u]=tot;
    e[++tot]={u,head[v],0,-cos};
    head[v]=tot;
}
pair<ll,ll> MCMF(int s,int t)
{
    ll flo=0, cos=0;
    while(1)
    {
        fill(dis,dis+maxn,INF);
        memset(inq,0,sizeof inq);
        queue<int> q;
        dis[s]=0;
        q.push(s);
        inq[s]=1;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            inq[u]=0;
            for(int i = head[u];i;i=e[i].nex)
            {
                int v=e[i].to;
                if(e[i].cap>0&&dis[v]>dis[u]+e[i].cos)
                {
                    dis[v]=dis[u]+e[i].cos;
                    pre[v]=i;
                    if(!inq[v]) 
                    {
                        q.push(v);
                        inq[v]=1;
                    }
                }
            }
        }
        if(dis[t]==INF) break;
        ll f=INF;
        for(int v=t;v!=s;v=e[pre[v]^1].to)
        {
            f=min(f,e[pre[v]].cap);
        }
        flo+=f;
        cos+=dis[t]*f;
        for(int v=t;v!=s;v=e[pre[v]^1].to)
        {
            e[pre[v]].cap-=f;
            e[pre[v]^1].cap+=f;
        }
    }
    return make_pair(flo,cos);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll c[55][55];
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            cin>>c[i][j];
        }
    }
    int s=0, t=2*n+1;
    tot=1;
    memset(head,0,sizeof head);
    for(int i = 1;i<=n;i++) add(s,i,1,0);
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            add(i,n+j,1,c[i][j]);
        }
    }
    for(int i = 1;i<=n;i++) add(n+i,t,1,0);
    pair<ll,ll> x1=MCMF(s,t);
    ll ansmin=x1.second;

    tot=1;
    memset(head,0,sizeof head);
    for(int i = 1;i<=n;i++) add(s,i,1,0);
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            add(i,n+j,1,-c[i][j]);
        }
    }
    for(int i = 1;i<=n;i++) add(n+i,t,1,0);
    pair<ll,ll> x2=MCMF(s,t);
    ll ansmax=-x2.second;
    cout<<ansmin<<'\n'<<ansmax;
}

最大流

P3376 【模板】网络最大流

其实顺序不太对，应该把MCMF的例题先讲完，但我有些懒得写。（后面会补的）

这题就是我们上文提到的最大流，也就是野兽先生那种，虽然说这个少了个限制，但是码量只增不减，还有（你会了模版可以过 $2$ 道蓝）。

这个东西的整体思路就是先用 BFS 建分层图，再用 DFS 在图上推流量，知道 BFS 发现这个 $s$ 到 $t$ 跑不通了，此时累加的费用就是最大流。

我们还可以增加一个弧优化来提升效率，减少重复跑边。

BFS 建分层图

先把深度都标为 $-1$ ，也就是未访问，再从源点出发跑有剩余容量的边，跑到了就给这个点打上层数（前面的点的层数 $+1$），所以 BFS 的规则就是只能从第 $k$ 层到第 $k+1$ 层，不能走环，跳层，回走。（不然 DFS只会绕圈）

bool bfs(int s,int t)//分层图，看看能否到汇点
{
    memset(dep,-1,sizeof dep);
    queue<int> q;
    q.push(s);
    dep[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i = head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}

DFS 多路增广

ll dfs(int u,int t,ll flo)//flo为当前流量上限
{
    if(u==t) return flo;
    ll used=0;//u推送出去的流量
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dep[v]==dep[u]+1)
        {
            ll f=dfs(v,t,min(flo-used,e[i].cap));
            if(f>0)
            {
                //更新网络
                e[i].cap-=f;
                e[i^1].cap+=f;//残量网络加回去代表可以反悔
                used+=f;
                if(used==flo) break;//推送满直接退出
            }
        }
    }
    return used;
}

我们函数里的 $flo$ 是 $flow$ 的意思，代表当前的流量上限，就是最多从 $u$ （当前点）往下送多少流量，$cur[u]$ 数组记录 $u$ 点遍历到哪条边，在这里我们引用了 $\&i$ 直接改 $cur[u]$，这样不会扫到增广过的边，使用 $used$ 后可以一次跑多条增广路，提高效率。

dinic

先 BFS 分层看能不能走得通，分完层要先重置当前弧，再反复跑 DFS 找到总最大流，再调用 BFS 分层（因为残量网络变化了）

ll dinic(int s,int t)
{
    ll mflo=0;//maxflow
    while(bfs(s,t))
    {
        memcpy(cur,head,sizeof cur);//分层后都要重置当前弧
        while(ll f=dfs(s,t,INF))
        {
            mflo+=f;
        }
    }
    return mflo;
}

这就是所有的重点了，其余的更新残量网络、建边和 MCMF 都是一样的。

#include <iostream>
#include <cstring>
#include <queue>
using namespace syh;
typedef long long ll;
const int maxn=205;
const int maxm=1e4+5;
const ll INF=1e18;
struct edge
{
    int to, nxt;
    ll cap;//这里不用管费用所以cost没了
}e[maxm];
int head[maxn], tot;
int dep[maxn];//BFS分层，点深度
int cur[maxn];//当前弧优化
void add(int u,int v,ll cap)
{
    e[++tot]={v,head[u],cap};
    head[u]=tot;
    e[++tot]={u,head[v],0};
    head[v]=tot;
}
bool bfs(int s,int t)//分层图，看看能否到汇点
{
    memset(dep,-1,sizeof dep);
    queue<int> q;
    q.push(s);
    dep[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i = head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
ll dfs(int u,int t,ll flo)//flo为当前流量上限
{
    if(u==t) return flo;
    ll used=0;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dep[v]==dep[u]+1)
        {
            ll f=dfs(v,t,min(flo-used,e[i].cap));
            if(f>0)
            {
                //更新网络
                e[i].cap-=f;
                e[i^1].cap+=f;//残量网络加回去代表可以反悔
                used+=f;
                if(used==flo) break;//推送满直接退出
            }
        }
    }
    return used;
}
ll dinic(int s,int t)
{
    ll mflo=0;
    while(bfs(s,t))
    {
        memcpy(cur,head,sizeof cur);//分层后都要重置当前弧
        while(ll f=dfs(s,t,INF))
        {
            mflo+=f;
        }
    }
    return mflo;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin>>n>>m>>s>>t;
    tot=1;
    memset(head,0,sizeof head);
    for(int i = 1;i<=m;i++)
    {
        int u, v, w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    cout<<dinic(s,t);
}

之前不是给大家提到了双倍经验吗，这里放下题目：

P2740 [USACO4.2] 草地排水 Drainage Ditches

你成功的又写了 $2$ 道蓝。

最小割

只写蓝怎么行，必须给老己整点好的。

P4177 [CEOI 2008] order

讲题之前呢，我们应该认识一下这个最小割，其实从它的名字也可以知道，就是把图给撕掉了，或者说撕成两半，左边的一半叫 $s$ ，右边一半叫 $t$ ，被撕开之前连接 $s$ 与 $t$ 的边就是割边，这个最小割就是割边里容量最小的割边的容量（长难句）。

我们有个定理，就是 最大流最小割定理（这名字好简洁）一个图里的最大流等于最小割。

为啥捏？

我们知道最大流是容量的瓶颈（必须流最小的不然大的容量小的流不了），最小割也是容量的瓶颈（都最小的肯定取的是最小的容量），由于瓶颈 $=$ 瓶颈，所以证毕。

那这个题里面，我们的割是啥？

我们建一个图来存：

1. $s$到任务（任务收益）
2. 任务到机器（租金）
3. 机器到 $t$ （买机器的钱）

在我们做完最小割后，如果任务 $i$ 在 $s$ ，那说明我们承接了这个任务，拿到了收益 $x_i$，如果它在 $t$ ，说明放弃了这比生意，收入获得了 $-x_i$（就是亏了 $x_i$），如果在 $t$ 的是机器 $k$，那么代表买了这台机器，割掉 $k→t$ ，付出 $y_k$ 的钱，由于我们买了这个机器，所以所有指向它的要付租金的边就不用割掉了。

最小割是啥咧？

题目里最小割的值就是我们 损失的钱的总和 ，那答案就是 总收入 $-$ 最小割。

这不就最大流吗？

那你套个模版试试呗。

好了过掉了。

#include <iostream>
#include <cstring>
#include <queue>
using namespace syh;
typedef long long ll;
const int maxn=3005;
const int maxm=2e7;
const ll INF=1e18;
struct edge
{
    int to, nxt;
    ll cap;//这里不用管费用所以cost没了
}e[maxm];
int head[maxn], tot=1;
int dep[maxn];//BFS分层，点深度
int cur[maxn];//当前弧优化
void add(int u,int v,ll cap)
{
    e[++tot]={v,head[u],cap};
    head[u]=tot;
    e[++tot]={u,head[v],0};
    head[v]=tot;
}
bool bfs(int s,int t)//分层图，看看能否到汇点
{
    memset(dep,-1,sizeof dep);
    queue<int> q;
    q.push(s);
    dep[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i = head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
ll dfs(int u,int t,ll flo)//flo为当前流量上限
{
    if(u==t) return flo;
    ll used=0;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dep[v]==dep[u]+1)
        {
            ll f=dfs(v,t,min(flo-used,e[i].cap));
            if(f>0)
            {
                //更新网络
                e[i].cap-=f;
                e[i^1].cap+=f;//残量网络加回去代表可以反悔
                used+=f;
                if(used==flo) break;//推送满直接退出
            }
        }
    }
    return used;
}
ll dinic(int s,int t)
{
    ll mflo=0;
    while(bfs(s,t))
    {
        memcpy(cur,head,sizeof cur);//分层后都要重置当前弧
        while(ll f=dfs(s,t,INF))
        {
            mflo+=f;
        }
    }
    return mflo;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin>>n>>m;
    int s=0, t=n+m+1;
    ll sum=0;
    for(int i = 1;i<=n;i++)
    {
        int xi, ti;
        cin>>xi>>ti;
        sum+=xi;//累计总收入用于减掉最小割
        add(s,i,xi);//源点s，任务i，容量xi
        for(int j = 1;j<=ti;j++)
        {
            int a, b;
            cin>>a>>b;
            //机器a的编号是n+a
            add(i,n+a,b);//任务i，机器a，容量b
        }
    }
    for(int k = 1;k<=m;k++)
    {
        int y;//买下机器的钱
        cin>>y;
        add(n+k,t,y);//机器k，汇点t，容量y
    }
    ll mincut=dinic(s,t);
    cout<<sum-mincut;
}

哎为啥只有 $70pts$ ，其实我觉得开 $2e5$ 就可以了但是题目硬是要开到 $2e7$ 。

这题因为大部分套的都是最大流的板子，所以没怎么改变注释，只把 main 函数部分的一些改变写了。

首紫献给网络流。

P2762 太空飞行计划问题

没错这又是一道紫。

这是一个最大闭合子图的板子。

让我们讲人话。

题意：

$m$ 个实验，$n$ 个仪器，$2$ 个选择。

1. 做实验 $e_i$，赚 $p_i$ 的钱。（必须买下要用的所有仪器）
2. 买仪器 $i_j$，花 $c_j$ 的钱。

净收益为总收入 $-$ 花的总钱数。

求最大收益，且要输出做哪些实验，买哪些仪器。

---

我们先要知道啥是闭合子图。

如果选中一个点，那么它所有能到达的后继点必须一起选中。

在这个题里：

• 实验是正权点 （收益 $p_i$）
• 仪器是负权点 (权值为 $-c_j$)
• 边：实验 $→$ 要用的仪器。（选了实验就要选仪器）

建图规则

现有超级源点 $s$ 与超级汇点 $t$ ，$s$ 连所有实验，每个实验向要买的仪器连（容量为 $INF$），仪器都连向 $t$，这里的 $INF$ 边不能割掉。（因为要满足依赖关系）。

我们累加所有收益为 $sum$，再用 $dinic$ 跑最小割记作 $mincut$，再减一减得到最大净收益 $ans$。

到这里都和最大流最小割一模一样。

---

那怎么输出实验和仪器捏？

跑完 $dinic$ 后，最后一次 BFS分层，$s$ 能到的点就是做了实验/买了仪器的点 。

其实这里我们在二分图里把 $s$ 用于存闭合子图（选中的），$t$ 用于存不选的点。

---

这里割的含义：

• 割掉 $s→e_i$ 放弃这个实验，损失 $p_i$ 的收益。
• 割掉 $i_j→t$ 购买这个仪器，支出 $c_j$ 的成本。
• $INF$ 边不会被割掉，只要实验选了那么对应的 $INF$ 边也会被选。

#include <iostream>
#include <cstring>
#include <queue>
using namespace syh;
typedef long long ll;
const int maxn=1005;
const int maxm=2e5;
const ll INF=1e18;
struct edge
{
    int to, nxt;
    ll cap;
}e[maxm];
int head[maxn], tot=1;
int dep[maxn];
int cur[maxn];
bool vis[maxn];//记录BFS可达点用于输出方案
void add(int u,int v,ll cap)
{
    e[++tot]={v,head[u],cap};
    head[u]=tot;
    e[++tot]={u,head[v],0};
    head[v]=tot;
}
bool bfs(int s,int t)
{
    memset(dep,-1,sizeof dep);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    dep[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i = head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                vis[v]=1;
                q.push(v);
                if(v==t) return true;
            }
        }
    }
    return dep[t]!=-1;
}
ll dfs(int u,int t,ll flo)
{
    if(u==t) return flo;
    ll used=0;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dep[v]==dep[u]+1)
        {
            ll f=dfs(v,t,min(flo-used,e[i].cap));
            if(f>0)
            {
                e[i].cap-=f;
                e[i^1].cap+=f;
                used+=f;
                if(used==flo) break;
            }
        }
    }
    return used;
}
ll dinic(int s,int t)
{
    ll mflo=0;
    while(bfs(s,t))
    {
        memcpy(cur,head,sizeof cur);
        while(ll f=dfs(s,t,INF))
        {
            mflo+=f;
        }
    }
    return mflo;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin>>m>>n;
    int s=0, t=n+m+1;
    ll sum=0;
    for(int i = 1;i<=m;i++)//实验编号1-m，仪器编号m+1-m+n
    {
        int p, x;
        cin>>p;
        sum+=p;
        add(s,i,p);
        while(cin>>x)
        {
            add(i,m+x,INF);
            if(cin.get()=='\n') break;
        }
    }
    for(int k = 1;k<=n;k++)
    {
        int c;
        cin>>c;
        add(m+k,t,c);
    }
    ll mincut=dinic(s,t);
    ll ans=sum-mincut;
    for(int i = 1;i<=m;i++)//输出选中的实验
    {
        if(vis[i]) cout<<i<<" ";
    }
    cout<<'\n';
    for(int i = 1;i<=n;i++)//输出选中的仪器
    {
        if(vis[m+i]) cout<<i<<" ";
    }
    cout<<'\n'<<ans;//输出答案
}

其实听懂了也就会写了，所以没写多少注释，不过这个题的 $2/3$ 都是用的最小割板子，紫++。