b23.tv 费用流
费用流¶
请先复习**网络流**的内容
EK算法¶
364 网络流 费用流 EK 算法_哔哩哔哩_bilibili
费用流 给定一个网络\(G=(V,E)\)，每条边有容量限制\(c(u,v)\)，还有单位流量的费用\(w(u,v)\)。 当\((u,v)\)的流量为\(f(u,v)\)时，需要花费\(f(u,v)\times w(u,v)\)的费用。 该网络中总花费最小的最大流称为最小费用最大流，总花费最大的最大流称为最大费用最大流，二者合称费用流模型，即在最大流的下考虑费用的最值。 一个网络的最大流是唯一的，不同路径有不同的费用。 我们用\(wf/c\)表示边的边权 流量/容量。
其中最大流指的是**总流量**最大，不是单独的一条路径
上图 最大费用最大流
下图 最小费用最大流
EK算法 在EK算法求解最大流的基础上，把“用BFS寻找一条增广路”改为“用spfa寻找一条单位费用之和最小的增广路”（即把\(w(u,v)\)当做边权，在残留网上求最短路），即可求出最小费用最大流。
与EK模板的区别
为了退流，反向边的初始容量为0，反向边的容量每次+ f 为了退费，反向边的初始费用为-w，走反向边的花费+\(f*(-w)\)
关于cost的修改
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int mf[N];//最大流量maxflow
int s,t,pre[N],n,m;
int cst,dis[N],vis[N];
struct edge{
int v,c,nxt,w;
}e[20*N];
int h[N],idx=1;//边的id从2开始存,因为边与残留边对应,使用i^1可以迅速在n与n+1之间相互转换(n为偶数),不用特判
void add(int a,int b,int c,int dd){
e[++idx]={b,c,h[a],dd};
h[a]=idx;
}
//***重要
bool spfa(){//找一条可以从s到t的有效路径
memset(dis,0x3f,sizeof dis);//最短路常规操作
dis[s]=0,vis[s]=1;//vis标记其是否在队内
memset(mf,0,sizeof mf);//将每个点能到达的流量上限变成0
queue<int> q;
q.push(s);mf[s]=1e9;//源点的流量上限为无穷大,即源点能为后面提供无限大的流量
while(q.size()){
int u=q.front();q.pop();vis[u]=0;
for(int i=h[u];i;i=e[i].nxt){//扫描出边
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w&&e[i].c){//如果 目前这条路到v比之前到v的路更短 并且存在这条边/这条边在之前走过但还有空余容量(容量>0)
dis[v]=dis[u]+w;
mf[v]=min(mf[u],e[i].c);//更新流量上限为之前更新过的可以到达u的流量(即点u能提供的最大流量)与u-v见之间的容量的min
pre[v]=i; //存目前路径上点v的前驱边
if(!vis[v])//防止重复入队
q.push(v),vis[v]=1;
//找增广路相当于找到一条新的流量到t,回顾二分图的增光路,之前已经找到的增光路的路径可以调整,但流量不会变化(即不会使之前已经有的流量减小)
}
}
}
if(mf[t])return 1;//如果有流量到达t,说明找到了一条增广路
else return 0;//一定要返回0!没有返回值会当作true处理!
}
//***
int EK(){
int nf=0;//当前总流量nowflow
while(spfa()){//新找到一条增广路,路的流量为mf[t] (流量是从s开始在到达t途中受到限制逐渐减小的,因此到达t的流量才是这条路的流量)
//cout<<'K';
int v=t;
while(v!=s){//从t往回在更新残留网
int i=pre[v];
e[i].c-=mf[t];//主边,空余的容量减少了
e[i^1].c+=mf[t];//残留边(反向边)
//此消彼长
v=e[i^1].v;
}
nf+=mf[t];//汇入一股新的流量
//***重要
cst+=mf[t]*dis[t];
//***
}
return nf;
}
signed main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w,dd;
cin>>u>>v>>w>>dd;
add(u,v,w,dd);add(v,u,0,-dd);
}
cout<<EK()<<' '<<cst<<endl;
}
仅仅以下更改
-
对于cost的统计与相关代码
-
将bfs找增光路变成spfa求最短路
为什么这个判定不能用了？
// use this at spfa最后
if(mf[t])return 1;//如果有流量到达t,说明找到了一条增广路
else return 0;//一定要返回0!没有返回值会当作true处理!
//instead of
if(v==t)return 1;//说明找到了一条增广路
那是因为之前bfs只是要求找到，于是只有一到达汇点就可以判定找到if(v==t)return 1;，而现在是要求找到最小的。因此只有完整的运行了一次spfa，才能判定有没有到汇点的新增流量
Dinic算法¶
同EK，将bfs改为spfa即可。
未验证的代码
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
struct Edge {
int to, rev;
long long cap, cost;
};
vector<vector<Edge>> graph;
vector<int> level, iter;
int n;
// 使用BFS构建分层图并返回是否能够到达汇点
bool bfs(int s, int t) {
level.assign(n, -1);
level[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int v = que.front(); que.pop();
for (auto& e : graph[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
return level[t] >= 0;
}
// DFS寻找增广路径并返回流量
long long dfs(int v, int t, long long f) {
if (v == t) return f;
for (int& i = iter[v]; i < graph[v].size(); ++i) {
Edge& e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
long long d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
// Dinic算法主函数，返回最大流，并更新总费用
long long dinic(int s, int t, long long& flowCost) {
long long maxFlow = 0;
flowCost = 0;
while (bfs(s, t)) {
iter.assign(n, 0);
long long f;
while ((f = dfs(s, t, INF)) > 0) {
maxFlow += f;
// 在这里更新费用，需要有一个费用数组来记录每条边的费用
// 假设我们有一个vector<long long> cost数组
for (int v = t; v != s; v = graph[v][graph[v][iter[v]].rev].to) {
flowCost += f * graph[v][graph[v][iter[v]].rev].cost;
}
}
}
return maxFlow;
}
int main() {
int m, s, t;
cin >> n >> m >> s >> t;
graph.assign(n, vector<Edge>());
for (int i = 0; i < m; ++i) {
int u, v, cap, cost;
cin >> u >> v >> cap >> cost;
graph[u].push_back({v, (int)graph[v].size(), cap, cost});
graph[v].push_back({u, (int)graph[u].size() - 1, 0, -cost});
}
long long flowCost = 0;
long long maxFlow = dinic(s, t, flowCost);
cout << "Max flow: " << maxFlow << endl;
cout << "Min cost: " << flowCost << endl;
return 0;
}
最小费用可行流¶
最小费用可行流指的是在费用流基础上给每条边的流量设置不仅有上限，还有下限。
见练习 | 这人怎么天天刷题啊（old）支线剧情
b23.tv 费用流