网络流初步

网络流

网络流简介

流量网络

若有向图G=(V,E)满足以下条件：
1.有且仅有一个顶点S,它的入度为0，那么这个顶点S便称为源点。
2.有且仅有一个顶点T,它的出度为0，那么这个顶点T便称为汇点。
3.每一条弧都有非负数，叫做该边的容量。边(vi,vj)的容量用cij表示。
则称之为网络流图，记为G=(V,E,C)。

网络流模型例子：
想要将一些水从S运到T，必须经过一些水站，连接水站的是管道，每条管道都有它的最大能容纳的水量，求S到T最多能流多少流量。

可行流

对于网络流G，每一条弧(i,j) 都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
满足以下三点：
1.每一条弧(i,j)有Fij<=Cij。即：对于每条边，流经该边的流量不得超过该边的容量(不撑爆水管)。
2.流量平衡：除源点S和汇点T以外的所有的点vi，即流入的流量等于流出的流量，即中转点不截流量。
3.对于源点S和汇点T有：S流出的流量等于T流入的流量。

增广路

之所以叫增广路，是因为增广路上弧的流量通过一定规则的修改，可以令整个流量放大，也就是多流流量。
给定一个可行流f = (fij),若fij = Cij,也就是已经流满了，称<vi,vj>为饱和弧，否则为非饱和弧。若fij = 0, 则称为零流弧，否则称为非零流弧。
定义一条道路P，起点为S，终点为T。把P上所有与P方向一致(流向终点)的弧定义为正向弧，正向弧全体记为P+；所有与P反向的弧定义为反向弧，全体记为P-。
定义一个可行流f，P是从S到T的一条道路，如果满足：
fij是非饱和流,并且<i,j>属于P+，fij是非零流，并且<i,j>属于P-。
那么称P是f的一条增广路。
下面来看一条增广路：

其中f={V1,V2}是一条可行流，画绿线的P是f的一条可改进路。我们可以通过让V2向V1反向流2的流量，使得最后从S到T多流2的流量。这里让V2流向V1实际上考虑的是我们将V1流向V2的流量还回去。
为什么要还回去呢？
如果我们不考虑还流量会发生什么情况？
假设一开始找增广路发生了下面这样的情况：

如果我们不考虑还流量，那么当发生上图现象时我们就没有办法从S到T多留任何流量了(因为此时水管已经满了)。
但如果我们还回去流量，则可以使得S到T多留2的流量，如下图：

于是我们从1向2流了2的流量，后又从2向1流了2的流量。实际上他们是抵消了，变成S -> 1 -> T流了2的流量，S -> 2 -> T流了2的流量。
这样操作的意义是哪怕我们一开始没有找到最优解的增广路，只要我们从 A -> B 流了X流量，我们就建立一条 B -> A 容量为X的反向边，让它之后再找增广路的过程中可以把流量还回去，避免发生刚才的状况，相当于给了一个反悔的机会。

残量网络

剩余的流量 + 反向平衡的流量共同构成残量网络。
定义：在不超过容量C(u,v)的条件下，从u到v之间可以压入额外的流量，就是(u,v)的残留流量。
残量网络就是将原图中的每一条边的边权更新为这条边最初的边权与流经这条边的流之差，除了修改正向的边权之外，还要将逆向边的边权改为目前流经这条边的流量。
如下图留个节点，七条边的有向图，红色代表一条增广路，其流量为3。/前面表示的是流量，后面表示的是这条边的容量。

对应的残量网络如下图所示：其中红色边是修改权值后的边，绿色边是建立的逆向边。最后一个(4,6)这条边由于红色边边权为零，所以直接删除了。

流量算法

最大流

在所有可行流中，最大流指其中流量最大的一个流的流量。

基本方法：每次去找增广路，并且维护残量网络，再去找增广路...直到找不到增广路，我们就找到了最大流。

最小割

割切

G = (V,E,C)是已知的网络流图，设U是V的一个子集，W = V\U,满足SU，TW。即U、W把V分成两个不相交的集合，且源点和汇点分属于不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用(U,W)表示。把(U,V)中所有弧的容量之和叫做次割切的容量，记为C(U,W)。

例如上图这个割切的容量为：1 + 2 + 2 + 4 = 9。
容量最小的割切称为最小割。

流量算法的基本理论

定理1.对于一直网络流图，设任意可行流为f，任意一割切为(U,W)，必有：V(f) <= C(U,W)(大于会把水管撑爆)。
定理2.可行流f是最大流的充分必要条件：f中不存在增广路(只要有增广路说明还可以多留流量)。
定理3.如果网络中所有弧的容量是整数，则存在整数值的最大流。
定理4.最大小最小割定理：最大流等于最小割，即max V(f) = min C(U,W)。(通俗理解：一根粗细不同的水管的最大流量取决于最细的那一段水管)。

建图

这里引用SNRainiar的建图方式:
使用链式前向星建图。

// 流量网络
int head[N];
struct e 
{
    int to, f, nxt;
} edge[M];

这里的f表示的是容量，但我们还需要知道当前这条边流了多少的流量。我们对每个有向边分别按照其容量 C 建立一条容量为 C 的正向边和一条容量为 0 的反向边。

当我们需要消耗边的流量时，只需要将正向边的流量减少，反向边的容量增加，并保证正向边和反向边的容量都不小于 0，那么就可以唯一确定一条边的容量和流量信息了。

inline void addEdge(int u, int v, int f) 
{
    edge[++head[0]] = {v, f, head[u]};
    head[u] = head[0];
    edge[++head[0]] = {u, 0, head[v]};
    head[v] = head[0];
}

由于我们需要同时修改正向边和反向边。所以我们可以利用异或操作来快速定位一条边的方向边。

需要注意的是我们需要使边的起始编号从 2 开始，因为 2、3 通过异或 1 就可以互相得到，而 0 标号在链式前向星中不能使用，所以其对应的 1 也不能使用。要设置编号从 2 开始，那么只需要在插边开始前令 head[0] 赋值为 1 即可,或者用cnt。

对于费用流网络流，我们还需要存储费用信息：

// 流量网络，边的序号应从1开始，使得通过异或运算就可以得到反流边
int head[N];
struct e 
{
    int to, f, c, nxt;
} edge[M];

对于费用网络的反向边其费用信息需要设置为负，这样在处理反向边的时候才能将积累的费用还原回去。

inline void addEdge(int u, int v, int f, int c) 
{
    edge[++head[0]] = {v, f, c, head[u]};
    head[u] = head[0];
    edge[++head[0]] = {u, 0, -c, head[v]};
    head[v] = head[0];
}

最大流算法

Dinic算法(常用)

Dinic算法是一个基于"层次图"的时间效率优先的最大流算法，时间复杂度 O(V^2E)。
层次，其实就是从S走到那个点的最短路径长度。
于是乎我们得到一个定理：从源点开始，在层次图中沿着边不管怎么走，经过的路径一定是在终点中剩余图中的最短路。

这里引用SNRainiar的Dinic模板:

// Dicnic算法本质上是优化的EK算法 O(V^2E)，适合稠密图
// Author：SNRainiar, from SZTU_AtDawn

#define MAX_N 100
#define MAX_M 10000
#define INF 0x3f3f3f3f

// 流量网络
int head[MAX_N];
struct e {
    int to, f, nxt;
} edge[MAX_M];

// 深度、当前弧
int dep[MAX_N], cur[MAX_N];
// 生成分层图
bool bfs(int s, int t) {
    memset(dep, 0, sizeof(dep));
    memcpy(cur, head, sizeof(cur));
    std::queue<int> que;
    que.emplace(s);
    dep[s] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = head[u]; i; i = edge[i].nxt)
            if (edge[i].f && !dep[edge[i].to]) {
                dep[edge[i].to] = dep[u] + 1;
                que.emplace(edge[i].to);
            }
    }
    return dep[t];
}
// 修改流量，使用当前弧优化
int dfs(int u, int t, int f) {
    if (!f || u == t)
        return f;
    int flow = 0;
    for (int i = cur[u]; flow < f && i; i = edge[i].nxt) {
        cur[u] = i;
        if (edge[i].f && dep[edge[i].to] == dep[u] + 1) {
            int tmp = dfs(edge[i].to, t, std::min(f - flow, edge[i].f));
            edge[i].f -= tmp;
            edge[i ^ 1].f += tmp;
            flow += tmp;
        }
    }
    return flow;
}
// Dinic主方法
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t))
        ans += dfs(s, t, INF);
    return ans;
}

注意初始化的时head[0]=1

例题：

P3376 【模板】网络最大流
题意：给出一个网络图，以及其源点和汇点，求出其网络最大流。

建模过程：

最大流的模板题，正常连边后直接跑Dinic即可,注意开long long以及初始化head[0] = 1。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=200+10,INF=0x3f3f3f3f;
int head[N];
struct e
{
    int to;
    ll f;
    int ne;
} edge[10010];
void add(int u, int v, int f)
{
    edge[++head[0]] = {v, f, head[u]};
    head[u] = head[0];
    edge[++head[0]] = {u, 0, head[v]};//反向边
    head[v] = head[0];
}
int dep[N], cur[N];
bool bfs(int s,int t)
{
    memset(dep, 0, sizeof dep);
    memcpy(cur, head, sizeof cur);
    queue<int> que;
    que.emplace(s);
    dep[s] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = head[u]; i;i = edge[i].ne)
        {
            if(edge[i].f && !dep[edge[i].to])
            {
                dep[edge[i].to] = dep[u] + 1;
                que.emplace(edge[i].to);
            }
        }
    }
    return dep[t];
}
ll dfs(int u ,int t, int f)
{
    if(!f || u==t)
        return f;

    ll flow = 0;
    for (int i = cur[u]; flow < f && i; i = edge[i].ne)
    {
        cur[u] = i;//弧优化
        if(edge[i].f && dep[edge[i].to] == dep[u] + 1)
        {
            ll tmp = dfs(edge[i].to, t, min(f - flow, edge[i].f));
            edge[i].f -= tmp;
            edge[i ^ 1].f += tmp;//反向边
            flow += tmp;
        }
    }
    return flow;
}
ll dinic(int s, int t)
{
    ll ans = 0;
    while(bfs(s,t))//找增广路
    {
        ans += dfs(s, t, INF);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    head[0] = 1;
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m;i++)
    {
        int u, v, f;
        cin >> u >> v >> f;
        add(u, v, f);
    }
    cout << dinic(s, t);
    return 0;
}

延伸：

假如有多个源点和多个汇点呢？

建模过程：

由于本题有多个源点和汇点，所以我们可以建立一个超级源点和超级汇点，将它们分别到源点、汇点连接容量无穷大的边(如果是费用流网络，还需要将费用设置为 0)，这样一来，我们只需要针对这一个超级源点和超级汇点来跑最大流等算法就可以得到网络总流量。

解决了这个问题后本题就是一个普通的最大流问题，我们将超级源点连向每个源点，每个汇点向超级汇点连边，其他正常连边，最后跑一遍Dinic求最大流即可。

最小费用最大流算法

保证S到T流量最大的前提下，所需的费用最小就是最小费用最大流。

SPFA-EK 算法

时间复杂度O(V^2 E^2)。
这里继续引用SNRainiar的SPFA-EK模板:

// 基于SPFA的最小费用最大流
// Author：SNRainiar, from SZTU_AtDawn

#define MAX_N 1000
#define MAX_M 10000
#define INF 0x3f3f3f3f

// 流量网络，边的序号应从1开始，使得通过异或运算就可以得到反流边
int head[MAX_N];
struct e {
    int to, f, c, nxt;
} edge[MAX_M];

// 最小费用路径、前驱节点、前驱边
int dis[MAX_N], prv[MAX_N], pre[MAX_N];
// 集合存在标志
bool vis[MAX_N];
// 寻找最小费用増广路（SPFA）
bool spfa(int s, int t) {
    std::queue<int> que;
    que.emplace(s);
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    memset(vis, false, sizeof(vis));
    vis[s] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = edge[i].nxt)
            if (edge[i].f && dis[edge[i].to] > dis[u] + edge[i].c) {
                dis[edge[i].to] = dis[u] + edge[i].c;
                prv[edge[i].to] = u;
                pre[edge[i].to] = i;
                if (!vis[edge[i].to]) {
                    vis[edge[i].to] = true;
                    que.emplace(edge[i].to);
                }
            }
    }
    return dis[t] != INF;
}
// SPFA_EK主函数 O(V^2 E^2)，实际情况远小于理论时间复杂度
std::pair<int, int> mcmf(int s, int t) {
    int cost = 0, flow = 0;
    while (spfa(s, t)) {
        int mn = INF;
        for (int i = t; i != s; i = prv[i])
            mn = std::min(mn, edge[pre[i]].f);
        flow += mn;
        cost += mn * dis[t];
        for (int i = t; i != s; i = prv[i]) {
            edge[pre[i]].f -= mn;
            // 反流边
            edge[pre[i] ^ 1].f += mn;
        }
    }
    return {cost, flow};
}

注意初始化的时head[0]=1

最大费用最大流

直接将费用取负套最小费用最大流，然后将答案取负。

例题：

P4015 运输问题

建图过程：

多源点：仓库多汇点：商店。需要用超级源点和超级汇点连接。超级源点像每个仓库连容量为ai，费用为0的边。每个商店像超级汇点连容量为bj费用为0的边。对于每个仓库，让它向所有店商店连容量为正无穷费用为Cij边，表示可以向该商店运货。由于题目需要求最小费用和最大费用。于是我们先求一遍最小费用最大流，然后再将费用取负数求一遍最大费用最大流即可。

题解代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=100+10,INF=0x3f3f3f3f;
const double eps=1e-8;
int a[N],b[N],c[N][N];
int head[N];
struct e
{
    int to, f, c, ne;
} edge[N * 10 * 2];
int dis[N], pre[N], prv[N];//最小费用路径，前驱节点，前驱边
bool vis[N];
void add(int u, int v, int f, int c)
{
    edge[++head[0]] = {v, f, c, head[u]};
    head[u] = head[0];
    edge[++head[0]] = {u, 0, -c, head[v]};
    head[v] = head[0];
}
bool spfa(int s,int t)
{
    queue<int> que;
    que.emplace(s);
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    vis[s] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for (int i = head[u]; i;i = edge[i].ne)
        {
            int v = edge[i].to;
            if(edge[i].f && dis[v] > dis[u] + edge[i].c)
            {
                dis[v] = dis[u] + edge[i].c;
                prv[v] = u;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = 1;
                    que.emplace(v);
                }
            }
        }
    }
    return dis[t] != INF;
}
pii mcmf(int s,int t)//时间复杂度O(V^2 E^2),实际情况远小于理论时间复杂度
{
    int cost = 0, flow = 0;
    while(spfa(s,t))
    {
        int mn = INF;
        for (int i = t; i != s; i = prv[i])
        {
            mn = min(mn, edge[pre[i]].f);
        }
        flow += mn;
        cost += mn * dis[t];
        for (int i = t; i != s;i = prv[i])
        {
            edge[pre[i]].f -= mn;
            edge[pre[i] ^ 1].f += mn;//反向边
        }
    }
    return {cost, flow};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    head[0] = 1;
    int m, n;
    cin >> m >> n;
    int s = m + n + 1, t = s + 1;//超级源点，超级汇点
    for (int i = 1; i <= m;i++)
    {
        cin >> a[i];
        add(s, i, a[i], 0);//超级源点向每个仓库连边
    }
    for (int i = 1; i <= n;i++)
    {
        cin >> b[i];
        add(i + m, t, b[i], 0);//每个仓库商店向超级汇点连边
    }
    for (int i = 1; i <= m;i++)
    {
        for (int j = 1; j <= n;j++)
        {
            cin >> c[i][j];
            add(i, j + m, INF, c[i][j]);//每个仓库像每个商店连边
        }
    }
    cout << mcmf(s, t).first << '\n';//最小费用最大流
    memset(head, 0, sizeof head);
    head[0] = 1;
    for (int i = 1; i <= m;i++)
    {
        add(s, i, a[i], 0);
    }
    for (int i = 1; i <= n;i++)
    {
        add(i + m, t, b[i], 0);
    }
    for (int i = 1; i <= m;i++)
    {
        for (int j = 1; j <= n;j++)
        {
            add(i, j + m, INF, -c[i][j]);//费用取负数
        }
    }
    cout << -mcmf(s, t).first;//最后答案记得取负数
    return 0;
}

最小割

容量最小的割切称为最小割。
个人理解：将一张网络流图割成两个不互相交的集合，其中S和T分属于不同集合的最小代价。

例题：

P2774 方格取数问题

题目描述：
有一个 m 行 n 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

由题意我们可以知道相邻格子的不能共存只能选其一，由于这个特殊的性质我们可以想到棋盘染色，将这块方格图染色成黑白两色。
05b4eda8f25038284505ff90ae2b4e6

那么如何建图呢？

建图过程：

我们将S向所有的黑色格子连边，所有的白色格子向T连边，对于相邻的黑白格子我们只能选择其一，要么选择黑色格子的数放弃白色格子里的数，要么选择白色格子里的数放弃黑色格子里的数。于是乎我们可以这么建图：

A和B为相邻的格子，这样建图表示A和B一定要割掉其中一个使得这条边满流，那么割掉的最小代价就为min(a,b)。那么我们对图跑一遍最大流，得到的就是最小割。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e4+10,INF=0x3f3f3f3f;
const double eps=1e-8;
int a[105][105],id[105][105], dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n, m;
bool check(int x,int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
int head[N];
struct e
{
    int to, f, ne;
} edge[N*N];
void add(int u, int v, int f)
{
    edge[++head[0]] = {v, f, head[u]};
    head[u] = head[0];
    edge[++head[0]] = {u, 0, head[v]};//反向边
    head[v] = head[0];
}
int dep[N], cur[N];
bool bfs(int s,int t)
{
    memset(dep, 0, sizeof dep);
    memcpy(cur, head, sizeof cur);
    queue<int> que;
    que.emplace(s);
    dep[s] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = head[u]; i;i = edge[i].ne)
        {
            if(edge[i].f && !dep[edge[i].to])
            {
                dep[edge[i].to] = dep[u] + 1;
                que.emplace(edge[i].to);
            }
        }
    }
    return dep[t];
}
int dfs(int u ,int t, int f)
{
    if(!f || u==t)
        return f;

    int flow = 0;
    for (int i = cur[u]; flow < f && i; i = edge[i].ne)
    {
        cur[u] = i;//弧优化
        if(edge[i].f && dep[edge[i].to] == dep[u] + 1)
        {
            int tmp = dfs(edge[i].to, t, min(f - flow, edge[i].f));
            edge[i].f -= tmp;
            edge[i ^ 1].f += tmp;//反向边
            flow += tmp;
        }
    }
    return flow;
}
int dinic(int s, int t)
{
    int ans = 0;
    while(bfs(s,t))//找增广路
    {
        ans += dfs(s, t, INF);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int sum = 0;
    int cnt = 0;
    head[0] = 1;
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= m;j++)
        {
            cin >> a[i][j];
            sum += a[i][j];
            id[i][j] = ++cnt;
        }
    }
    int s = n*m + 1, t = s + 1;
    for (int i = 1;i<=n;i++)
    {
        for (int j = 1; j <= m;j++)
        {
            if((i+j)%2==0)
            {
                add(s, id[i][j], a[i][j]);

                for (int k = 0; k < 4;k++)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(check(x,y))
                    {
                        add(id[i][j], id[x][y], INF);
                    }
                }
            }
            else
            {
                add(id[i][j], t, a[i][j]);
            }
        }
    }
    int ans = dinic(s, t);
    cout << sum - ans;
    return 0;
}

常见技巧

点权转边权

如果题目给的是点权，我们可以将一个点拆成两个点，入点和出点(源点和汇点不用拆)。如果A和B连边，则A的出点连B的入点。

超级源点和超级汇点

超级源点连多个源点，多个汇点连超级汇点。

棋盘染色(二分图)

利用二分图性质。

题单

序号	题号	标题	题型	难度评级
1	P3376	【模板】网络最大流	最大流模板测试	⭐
2	P3381	【模板】最小费用最大流	最小费用最大流模板测试	⭐
3	P2756	飞行员配对方案问题	最大流	⭐⭐
4	P3254	圆桌问题	最大流	⭐⭐
5	P3171	[CQOI2015]网络吞吐量	最大流	⭐⭐⭐
6	P2766	最长不下降子序列问题	最大流	⭐⭐⭐⭐
7	P5771	反质数序列	最大流	⭐⭐⭐⭐⭐
8	P3163	危桥	最大流	⭐⭐⭐⭐⭐⭐
9	P5038	奇怪的游戏	最大流	⭐⭐⭐⭐⭐⭐
10	P4016	负载平衡问题	费用流	⭐⭐
11	P4015	运输问题	费用流	⭐⭐
12	P1251	餐巾计划问题	费用流	⭐⭐⭐
13	P4013	数字梯形问题	费用流	⭐⭐⭐
14	P3356	火星探险问题	费用流	⭐⭐⭐⭐
15	P2774	方格取数问题	最小割	⭐⭐⭐⭐
16	P3355	骑士共存问题	最小割	⭐⭐⭐⭐
17	P2765	魔术球问题	最小割	⭐⭐⭐⭐
18	P2057	善意的投票	最小割	⭐⭐⭐⭐
19	P4174	最大获利	最小割	⭐⭐⭐⭐
20	P2764	最小路径覆盖问题	最小割	⭐⭐⭐⭐⭐

题解

https://www.cnblogs.com/menitrust/p/16871227.html

标签：head,int,网络,流量,初步,dep,edge,que
From： https://www.cnblogs.com/menitrust/p/17347010.html

网络流

网络流简介

流量网络

可行流

增广路

残量网络

流量算法

最大流

最小割

割切

流量算法的基本理论

建图

最大流算法

Dinic算法(常用)

例题：

建模过程：

参考代码：

延伸：

建模过程：

最小费用最大流算法

SPFA-EK 算法

最大费用最大流

例题：

建图过程：

题解代码：

最小割

例题：

建图过程：

参考代码：

常见技巧

点权转边权

超级源点和超级汇点

棋盘染色(二分图)

题单

题解

相关文章

赞助商

阅读排行