模板及讲解

最大流问题

容量：一条边$(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;
}