网络流 学习笔记

模板及讲解

最大流问题

  • 容量:一条边$(u,v)$的上限记为$c(u,v)$.(如果边不存在,值为0)
  • 流量:一条边$(u,v)$运送的物品记为$f(u,v)$, $f(u,v)=-f(v, u)$(斜对称性)
  • 流量平衡:$\sum_{(u,v) \in E} f(u,v)=0$

(并且$f(u,v) \leq c(u,v))​$

最大流$Dinic$算法$O(n^2m)$

  • 残量网络:图中每条边上容量和流量之差构成一张新图,称为残量网络(反向弧也要计算)
  • 增广路:增广路是一条从源点到汇点路径上的剩余容量都大于$0$的简单路径
  • 增广路定理(最大流定理):如果残量网络不存在增广路,则当前流为最大流
  • 分层图:以从原点到某点的最短距离分层的图,距离相等的为一层
  • 多路增广:一次BFS进行多次增广
  • 最大可改进量:此次增广最大可以使得增广路的流量增加的量。

Dinic算法的大致思路:
1 先BFS对残量网络进行分层(根据从$S$到点$i$的距离分层,这些和$S$距离相等的点$i$都是一层的)。(初始的图也算一个残量网络)
2 然后再DFS进行多路增广(好处是如果两条不同增广路很长,但是重合了一大半,就不用两次BFS),如果增广到了$T$或者当前最大可改进量(最小残量)等于0就要终止DFS,否则在残量网络上进行增广,必须按照层次来增广,如果路径可以增广,那么路径上的边流量加去最大可改进量(最小残量),反向弧减去最大可改进量(最小残量),因为流量平衡

还可以进行优化,当前弧优化。如果一个点已经增广了一些边,那么这些边在下次DFS的时候不需要再被考虑。

Dinic模板代码见相关代码部分。loj #101
相关学习文章

写时注意:
1 边数组大小。(有一次ins就得乘一次2,最好用vector存)
2 拆点后点数组大小。
3 加边的时候如果无向,则反向弧容量为$c$,否则为$0$

最小割

最小割的流量$f(s,t)$=最大流

在找不到增广路之后,分层了的节点就是 $S$,没分层的点就是 $V-S=T$,即$s-t$割中的两个不相交集合${S, T}$

最大流$flow$是$s-t$最大流,$(S, T)$是$s-t$最小割

最小割的题目:USACO 5.4.3

Dinic求最大流,loj #101

//2019.1.11 upd: 使 cap 只表示残量
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000000 + 5, MAXM = 4000000 + 5, INF = 2147483647;
struct data {
    int v, cap;//终点,残量
}ed[MAXM * 2];
int n, m, s, t, maxd;
vector<int> G[MAXN];
int en, cur[MAXN], d[MAXN];//边数,当前弧(用于优化),距离S的距离,访问标记 
void ins(int u, int v, int c) {//加双向边 
    ed[en] = (data){v, c}, G[u].push_back(en++);
    ed[en] = (data){u, 0}, G[v].push_back(en++);//反向弧容量为0!不是-c,流量才是守恒的 
}
bool bfs() {//求分层图 
    queue<int> q; 
    for (int i = 0; i <= maxd; i++) d[i] = INF;
    d[s] = 0, q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap;
            if (d[v] == INF && cap) {//没被分层并且可以改进 
                d[v] = d[u] + 1;//分层 
                q.push(v); 
            }
        }
    }
    return d[t] != INF;//如果存在增广路则t会被访问 
}
LL dfs(int u, int a) {//多路增广 
    if (u == t) return a;//增广到终点
    if (a == 0) return 0;//没有可改进量
    LL retflow = 0;
    for (int &i = cur[u]; i < G[u].size(); i++) {
        int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap;
        if (d[u] + 1 == d[v]) {//按层次增广
            int f = dfs(v, min(a, cap)); //继续增广 
            if (f > 0) {//能够改进
                retflow += f, a -= f, ed[G[u][i]].cap -= f, ed[G[u][i] ^ 1].cap += f;//改进
                if (a == 0) break;//优化:没有可改进量时此点应该不再访问 
            }
        }
    }
    return retflow;
}
LL dinic() {//求最大流 
    LL flow = 0;
    while (bfs()) {
        for (int i = 0; i <= maxd; i++) cur[i] = 0; //DFS完以后要清空当前弧
        flow += dfs(s, INF);
    }
    return flow;
}
void clean() {
    en = 0;
    for (int i = 0; i <= n; i++) G[i].clear();
}
void solve() {
    clean();
      maxd = n;
    for (int u, v, c, i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &c);
        ins(u, v, c);
    }
    printf("%lld\n", dinic());
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t), solve();
    return 0;
}

费用流

现在给出的网络每天边有单位流量的代价,那么有以下问题:

  • 最小费用最大流:就是在最大流的前提下的最小费用的流
  • 最大费用最大流:就是在最大流的前提下的最大费用的流

可以使用 EK+Spfa 求费用流。即用 Spfa 找到一条代价最小的增广路不断增广。
代码:loj #102

写时注意:

1、Spfa 记得取消 vis的标记
2、反向弧的价值相反,否则死循环

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 400 + 5;
    const int INF = 2147483647;

    struct edge {
        int u, v, cap, w, nxt;
    } ed[30000 + 5];

    int n, m, hd[MAXN], en, s, t;
    int dis[MAXN], incf[MAXN], pre[MAXN], vis[MAXN], flow, cost;
    // dis[i]: s 到 i 最短路。incf[i]:s 到 i 可改进量。pre[i]:i 的前驱边。 

    void ins_c(int u, int v, int cap, int w) { // 加一条边 
        ed[++en] = (edge){u, v, cap, w, hd[u]}, hd[u] = en;
        ed[++en] = (edge){v, u, 0, -w, hd[v]}, hd[v] = en; // 对称费用 
    }
    queue<int > q;
    bool spfa() { // Spfa 找到一条增广路 
        for (int i = 0; i <= n; ++i) dis[i] = INF, incf[i] = INF, vis[i] = 0, pre[i] = -1;
        vis[s] = 1, dis[s] = 0, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop(); 
            vis[u] = 0; // 不要忘记 
            for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (dis[u] != INF && dis[e.v] > dis[u] + e.w && e.cap) {
                    dis[e.v] = dis[u] + e.w;
                    pre[e.v] = i;
                    incf[e.v] = min(incf[u], e.cap);
                    if (!vis[e.v]) vis[e.v] = 1, q.push(e.v);
                }
            }
        }
        return dis[t] != INF;
    }
    void update() { // 有增广路则更新流量并且统计流量和费用 
        int now = pre[t];
        while (now != -1) {
            ed[now].cap -= incf[t];
            ed[now ^ 1].cap += incf[t]; // 注意对称 
            now = pre[ed[now].u];
        }
        flow += incf[t];
        cost += dis[t] * incf[t];
    }

    void clean() {
        en = -1, ms(hd, -1), cost = flow = 0;
    }
    int solve() {

        clean();

        scanf("%d%d", &n, &m);
        s = 1, t = n;
        for (int u, v, cap, w, i = 1; i <= m; ++i) {
            scanf("%d%d%d%d", &u, &v, &cap, &w);
            ins_c(u, v, cap, w);
        }

        while (spfa()) update();

        printf("%d %d\n", flow, cost);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

网络流相关模型

点拆成边

点权转边权
1、poj 3422 K-方格取数

拆边

边权只有一次流量有效
1、Loj 6224「网络流 24 题」深海机器人问题
2、poj 3422 K-方格取数

网格图

网格图问题
1、Loj 6224「网络流 24 题」深海机器人问题
2、poj 3422 K-方格取数

最短路

利用容量限制
1、poj 3422 来回最短路问题

资源

资源调配
1、Loj 6008 「网络流 24 题」餐巾计划

最小割相关

最大权闭合子图

有一个有向图,每一个点都有一个权值$w_i$(可以为正或负或$0$),选择一个权值和最大的子图,使得每个点的后继都在子图里面,这个子图就叫最大权闭合子图。

这些点可以抽象为一个个事件互相依赖的关系。

求法:正权点连边$(S, i)$容量为$w_i$,负权点连边$(i, T)$容量为$|w_i|$,将原图边保留,容量为$INF$。
然后对图最小割$c[S, T]$,最后答案即为$\sum\limits_{1 \leq i \leq n, w_i \leq 0} w_i - c[S, T]$

对图最小割本质上就是
如果切断$S​$与点的边,即为不要这个点,减去这个点的收益
如果切断$T$与点的边,即为这个点,加上不必要的成本

1、Bzoj 1497 「NOI2006」最大获利=CF 1082G

------ 本文结束 ------