总结 网络流

网络最大流以及最小费用最大流板子，以及一点网络流的总结。

非常好的博客：xht37's blog。

Dinic 算法

网络最大流

记得加当前弧优化。

int n, m, cnt = 1, s, t;
int head[N], deep[N], cur[N];
Edge e[N<<2];
bool inq[N];
queue<int> q;

inline bool bfs() {
    for (int i = 1; i <= n; ++i)
        cur[i] = head[i];
    memset(deep, 0x3f, sizeof deep);
    q.push(s), inq[s] = true;
    deep[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (deep[v] > deep[u] + 1 && e[i].flow) {
                deep[v] = deep[u] + 1;
                if (!inq[v])
                    q.push(v), inq[v] = true;
            }
        }
    }
    return deep[t] != INF;
}

int dfs(int u, int flow) {
    if (u == t || !flow)
        return flow;
    int rlow, v, re = 0;
    for (int i = head[u]; i; i = e[i].nxt) {
        v = e[i].to;
        if (deep[v] == deep[u] + 1 && e[i].val && (rlow = dfs(v, min(flow, e[i].val)))) {
            e[i].val -= rlow, e[i^1].val += rlow;
            flow -= rlow, re += rlow;
            if (!flow) break;
        }
    }
    if (!re) deep[u] = -1;
    return re;
}

inline int Dinic() {
    int maxflow = 0, now;
    while (bfs()) {
        while ((now = dfs(s, INF))
        	maxflow += now;
    }
    return maxflow;
}

费用流

需要注意加边时反向边费用取负。

const int N = 1e4 + 9;
const int M = 1e5 + 9;
const int INF = 0x3f3f3f3f;

struct Graph {
    int cnt;
    int head[N], cur[N], nxt[M], to[M], flow[M], cost[N];
    Graph() { cnt = 1; }
    inline void add(int u, int v, int w, int c) {
        ++cnt, nxt[cnt] = head[u], to[cnt] = v, flow[cnt] = w, cost[cnt] = c, head[u] = cnt;
        ++cnt, nxt[cnt] = head[v], to[cnt] = u, flow[cnt] = 0, cost[cnt] = -c, head[v] = cnt;
    }
} G;

int n, m, S, T, maxflow, mincost;
int dis[N], flow[N];
bool inq[N], vis[N];
queue<int> q;

inline bool bfs() {
    for (int i = 1; i <= n; ++i) dis[i] = INF, inq[i] = false;
    for (int i = 1; i <= n; ++i) G.cur[i] = G.head[i];
    dis[S] = 0;
    q.push(S), inq[S] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int i = G.head[u]; i; i = G.nxt[i]) {
            int v = G.to[i];
            if (G.flow[i] > 0 && dis[v] > dis[u] + G.cost[i]) {
                dis[v] = dis[u] + G.cost[i];
                if (!inq[v]) q.push(v), inq[v] = true;
            }
        }
    }
    return dis[T] < INF;
}

int dfs(int u, int limit) {
    if (u == T || !limit) return limit;
    vis[u] = true;
    int rest = limit;
    for (int &i = G.cur[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (vis[v] || dis[v] != dis[u] + G.cost[i] || !G.flow[i]) continue;
        int rlow = dfs(v, min(G.flow[i], rest));
        if (!rlow) dis[v] = -1;
        mincost += rlow * G.cost[i];
        G.flow[i] -= rlow, G.flow[i ^ 1] += rlow;
        rest -= rlow;
        if (!rest) break;
    }
    vis[u] = false;
    return limit - rest;
}

inline void Dinic() {
    int rlow;
    while (bfs()) {
        while ((now = dfs(S, INF))) maxflow += now;
    }
}

附 EK 费用流（弃）。

上下界网络流

无源汇上下界可行流

每条边 \(i\) 流量限制范围 \(l_i,r_i\)。

先满足所有 \(l_i\)，这样会导致点的出入流量不守恒，所以建出超级源汇点 \(S,T\)。

设 \(d_u=\sum in_u-\sum out_u\)，若 \(d_u>0\) 则 \(S\) 向 \(u\) 连边，若 \(d_u<0\) 则 \(u\) 向 \(T\) 连边。

然后每条边的流量设为 \(r_i-l_i\)，就去掉了下界。

跑最大流，设 \(s=\sum out_S=\sum in_T\)，若最大流等于 \(s\) 则存在可行解。

若有解，每条边的流量 + 下界即为一组可行解。

有源汇上下界可行流

从 \(T\) 到 \(S\) 连一条 \([0,+\infty)\) 的边，转化为无源汇上下界可行流。

有源汇上下界最大流

先从 \(T\) 到 \(S\) 连一条 \([0,+\infty)\) 的边，从虚拟源点到虚拟汇点跑最大流判断是否有解。

若有解的话，断掉 \(T\) 到 \(S\) 的边，在残量网络上从 \(S\) 到 \(T\) 跑最大流，加上上一次的最大流即为答案。

感性理解，不会证。