title: 费用流
tags: 算法
date: 2022-11-23 05:21:28
本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。
简介
费用流是网络流的拓展，一般用于求解一些多次取点的问题。
前置知识
- 网络流
- 最短路
讲解
定义
在网络流中，在花费费用最小时的最大流。
如果有冲突，则优先满足最大流。
实现
大体逻辑和网络流区别不大，只是将算法中的 bfs 改为spfa或其他最短路算法，以费用为边权搜索最短路。
费用流算法可以基于 EK 和 Dinic 改来，下面这一版是基于 Dinic 更改而来的。
bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis)); // 初始化距离数组
memcpy(cur, lnk, sizeof(lnk)); // 复制数组状态
queue<int> q; // 正常的spfa
q.push(s), dis[s] = 0, vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i]; // 队首节点
if (cap[i] && dis[v] > dis[u] + cost[i]) {
dis[v] = dis[u] + cost[i]; // 注意这里是以费用为单位更新
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return dis[t] != INF; // 代表是否可以到达汇点
}
int dfs(int u, int t, int flow) {
if (u == t) return flow; // 搜索结束
vis[u] = 1; // 标记已访问
int ans = 0;
for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i]; // 队首节点
if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
int x = dfs(v, t, min(cap[i], flow - ans)); //
if (x)
ret += x * cost[i], // 单位费用
cap[i] -= x, // 正向边减流
cap[i ^ 1] += x, ans += x; // 反向边增流
}
}
vis[u] = 0; // 撤销标记状态，方便下一次
return ans;
}
int solve(int s, int t) {
int ans = 0;
while (spfa(s, t)) { // 这里进行了改动，将原先的bfs改成了spfa
int x;
while ((x = dfs(s, t, INF))) ans += x; // 一次dfs多次增流
}
return ans;
}
// 最后费用为ret
例题
P1004-[NOIP2000-提高组]-方格取数
P2045 方格取数加强版
这道题的难点在于构建费用流网络，首先分析题目性质：
- 一个格子只能取一次数字
- 可以走多次
根据这些可以构建出第一个图：
在每个点的连接处连流量为 \(2\) ，费用为 \(-val_i\) 的边，然后跑最大流。
先别急着翻到下面去，这个构建方法显然是错误的，因为没有考虑到走的次数，并且一个点可能被统计多次。
所以便有了下面这种方法。
首先，我们需要拆S,T点并添加限流才能确保没问题。
还有一点就是像 1->1' 这里要连两条边，第一条容量 \(1\) 费用 \(0\) 确保联通，第二条容量 \(1\) 费用 \(-val_i\) 才是实际能取到的价值
最后的图就是这样。
其实不管是网络流，还是费用流，最难的部分都是构建图，需要多理解为什么这么构建才能过这道题，只要理解了，那这一类的题型都不是什么难事。
代码写的有点丑，见谅。
s = 0, t = 2*n*n + 1;
addedge(s, 1, k,0); // 源点连 (1,1)
addedge(2*n*n, t, k,0); // (n,n) 的出点连汇点
for(int i=1;i<=n*n;i++){ // 先输入
scanf("%d",&val);
addedge(i,i+n*n,1,-val); // 因为这个点只能取一次
addedge(i,i+n*n,k-1,0); // 其他时候也需要联通
}
for(int i=1;i<=n*n;i++){ // 然后枚举每个点
if((i - 1) / n + 1 != n)
addedge(i+n*n,i+n,k,0); // 出点连下面的入点
if((i - 1) % n + 1!=n)
addedge(i+n*n,i+1,k,0); // 出点连左边的入点
}
printf("%d",dinic(s,t));
P1251 餐巾计划问题
这道题目的构建方法很新颖，单独提出来讲一下。
最大的问题是区分干净的餐巾和脏餐巾，这里可以将一天拆成早上和晚上。
首先要保证这里的流量，也就是每天早上的餐巾数量达标。
所以这里可以从每天早上向汇点连边，流量为当天需要的餐巾数量，费用为\(0\)。
还要从每天早上到每天晚上连边，容量为当天需要的餐巾数量，费用为\(0\)。
再根据题目的规则，很容易想到每天早上到下一天早上，每天晚上到下一天晚上连边，流量\(inf\)，费用\(0\)（保留干净的餐巾和脏餐巾）。
然后考虑送洗，中间的变化是 脏餐巾 -> 干净餐巾，所以可以从每天晚上到 当前天数+快洗天数的早上 连一条边，流量\(inf\),费用为快洗费用，慢洗同理。
购买餐巾也很简单，就从源点往每天早上连边，流量\(inf\)，费用为购买餐巾费用。
贴上核心代码：
int night(int i){return i+n;} // 每天晚上的编号
for (int i = 1; i <= n; i++)
{
scanf("%d", &tmp); // 每天需求的餐巾数量
addedge(i, t, tmp, 0); // 保证餐巾数量足够
addedge(s, night(i), tmp, 0); // 使用完的餐巾变成脏餐巾
}
scanf("%d%d%d%d%d", &pp, &mm, &f, &nn, &ss);
for (int i = 1; i <= n; i++)
{
addedge(s, i, INF, pp); // 购买餐巾
if (i + 1 <= n)
{
addedge(i, i + 1, INF, 0); // 保留干净餐巾
addedge(night(i), night(i + 1), INF, 0); // 保留脏餐巾
}
if (i + mm <= n)
addedge(night(i), i + mm, INF, f); // 快洗
if (i + nn <= n)
addedge(night(i), i + nn, INF, ss); // 慢洗
}