[图论入门]费用流

2023-12-16 18:57:51

#0.0 概述 & 前置知识

费用流 ，也叫作最小费用最大流，是指在普通的网络流图中，每条边的流量都有一个单价，求出一组可行解，使得在满足它是最大流的情况下，总的费用最小。

[图论入门]网络最大流 - 增广路算法
发表于 2021-06-18 20:25 Dfkuaid
摘要：网络最大流 FF,EK,Dinic 算法的简单讲解

阅读全文
>>

#1.0 SPP 算法

\(\texttt{SSP}\)（\(\texttt{Successive Shortest Path}\)）算法：在最大流的 \(\texttt{EK}\) 算法求解最大流的基础上，把 用 \(\texttt{BFS}\) 求解任意增广路 改为 用 \(\texttt{SPFA}\) 求解单位费用之和最小的增广路 即可。—— OI Wiki

#1.1 思路

简单来讲，\(\texttt{SPP}\) 算法就是 \(\texttt{EK+SPFA}\)，也就是将原本的 \(\texttt{BFS}\) 换成 \(\texttt{SPFA}\) 即可。来考虑这么做的正确性。

\(\texttt{EK}\) 算法的 \(\texttt{BFS}\) 过程本身就是寻找一条可行的增广路，而 \(\texttt{SPFA}\) 本身是寻找一条从源点到汇点的价格之和最小的一条路径，由此可知，我们只需要对 \(\texttt{SPFA}\) 的过程加一些约束，让它每次扩展出的路径都是一条残量网络上的可行路径（即剩余流量不为 \(0\)）即可。

注意在反向边的费用应当为正向边的费用的相反数。但要是产生负环怎么办？注意到，上面我们要求 \(\texttt{SPFA}\) 每次拓展出的路径都是存在残量的路径，所以如果存在负环且可以被拓展的话，那么意味着我们确实存在可以增广的路径，而当这条路径被增广结束后，这个负环也就不存在了（实际上负环仍然存在，但因为没有剩余流量，不会形成可进入的负环）。

至于为啥不用 \(\texttt{Dijkstra}\) 算法，显然是因为存在负边权，但我们可以通过一些操作避开这一点。但应该不会有出题人在这种问题上卡 \(\texttt{SPFA}\) 吧……

#1.2 代码实现

#define mset(l, x) memset(l, x, sizeof(l))

const int N = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v;
    int c, w;
    int nxt;
};
Edge e[N];

int n, m, s, t, cnt = 2, head[N];
int dist[N], inq[N], pre[N];
int q[N], frt, tal, maxflow, res;

template <typename T>
inline T Min(const T a, const T b) {
    return a < b ? a : b;
}

template <typename T>
inline T Max(const T a, const T b) {
    return a > b ? a : b;
}

inline void add(int u, int v, int w, int c) {
    e[cnt].u = u, e[cnt].v = v;
    e[cnt].w = w, e[cnt].c = c;
    e[cnt].nxt = head[u], head[u] = cnt ++;
}

bool SPFA() {
    mset(dist, 0x3f); mset(inq, 0);
    mset(pre, 0); frt = 0, tal = -1;
    q[++ tal] = s, inq[s] = 1, dist[s] = 0;
    while (frt <= tal) {
        int now = q[frt ++]; inq[now] = 0;
        for (int i = head[now]; i; i = e[i].nxt)
          if (e[i].w && dist[e[i].v] > dist[now] + e[i].c) {
              //加上对剩余流量的约束
              dist[e[i].v] = dist[now] + e[i].c;
              pre[e[i].v] = i;
              if (!inq[e[i].v]) {
                  inq[e[i].v] = true,
                  q[++ tal] = e[i].v;
              }
          }
    }
    return dist[t] != INF; //有无可行流
}

void update() {
    int flow = INF, i;
    for (int u = t; u != s; u = e[i ^ 1].v)
      i = pre[u], flow = Min(flow, e[i].w);
    for(int u = t; u != s; u = e[i ^ 1].v) {
        i = pre[u], e[i].w -= flow;
        e[i ^ 1].w += flow;
        res += e[i].c * flow;
    }
    maxflow += flow;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i ++) {
        int u, v, w, c;
        scanf("%d%d%d%d", &u, &v, &w, &c);
        add(u, v, w, c); add(v, u, 0, -c);
    }
    while (SPFA()) update();
    printf("%d %d", maxflow, res);
    return 0;
}

#2.0 应用

#2.1 二分图最大权完美匹配

设立一个超级源点和一个超级汇点，超级源点向所有左图的点连一条容量为 \(1\)，费用为 \(0\) 的边，所有右图的点向超级汇点连一条容量为 \(1\)，费用为 \(0\) 的边；假设边 \(a\to b\) 权值为 \(c\)，那么就由 \(a\) 向 \(b\) 连一条容量为 \(1\)，费用为 \(-c\) 的边，在此图上跑 \(\texttt{SPP}\) 算法即可。

正确性显然，不证。

参考资料

[1] [整理]网络流随记——中（费用流） - _ajthreac_

码农公寓