费用流略解
juruo999
·
·
个人记录
费用流
极好体验
前置知识：网络流
这里讲最小费用最大流 ( Minimum Cost Maximum Flow, MCMF )
定义
在网络流的基础上，每条边有一个单位费用，每条边的费用是它的流量乘上单位花费。我们用 (u,v,w,c) 来表示从 u 到 v 最大流量为 w 单位费用为 c 的一条边。
最小费用最大流问题就是要找到一个最大流，使得在流量最大的基础上，它的所有边费用和最小。
方法
讲两种：SSP 与 Primal-Dual
zkw流我不会所以不讲
SSP
非常非常非常简单
在 Dinic 的基础上，贪心沿着费用最小路增广。
注意建反向边时要把费用取相反数。
Primal-Dual
以下所有 w_{ij} 指边 (i,j) 的费用
原始对偶，好写好调跑得快，就是不知道名字啥意思。
因为反向边的存在，我们不得不面对负权边，所以我们不得不使用死去的 SPFA。但是 SPFA 慢，我们要用 Dijkstra！
为了使边权非负，我们考虑给每条边增减边权，我们想到给每一个点一个势函数 h_i，每条边的边权变为 w^\prime_{ij}=w_{ij}+h_i-h_j。
令 G 指每条边 (i,j) 权值为 w_{ij} 的图，G^\prime 指每条边 (i,j) 权值为 w^\prime_{ij} 的图，然后我们得到 G^\prime 中路径 i_1,i_2,\cdots,i_q 长度为
\begin{aligned}
&w^\prime_{i_1,i_2}+w^\prime_{i_2,i_3}+\cdots+w^\prime_{i_{q-1},i_q} \\=&w_{i_1,i_2}+h_{i_1}-h_{i_2}+w_{i_2,i_3}+h_{i_2}-h_{i_3}+\cdots+w_{i_{q-1},i_q}+h_{i_{q-1}}-h_{i_q}\\
=&w_{i_1,i_2}+w_{i_2,i_3}+\cdots+w_{i_{q-1},i_q}+h_{i_1}-h_{i_q}
\end{aligned}
接下来是如何维护势函数。我们发现若 $d_i$ 为 $G$ 中 $s$ 到 $i$ 最短路长度，则有 $d_j\le d_i+w_{ij}$，变形一下就是 $w_{ij}+d_i-d_j\ge0$，因此 $d$ 就可以作为初始的势函数 $h$。
然后每次跑 `Dijkstra` 得到的 $G$ 中的距离 $d_i$ 作为新的 $h$ 即可。
**划重点**：`Dijkstra` 出来的是 $G^\prime$ 的距离 $d^\prime_i$，而 $d_i=d^\prime_i+h_s-h_i=d^\prime_i-h_i$，所以 $h_i+d^\prime_i=d_i$，所以代码里是累加。
```cpp
// P3381 Luogu
// Graph Theory
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
namespace cflow{ // 奇异的空行充满了代码, 112 行
const int maxn=5005,maxm=50005;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,s,t;
inline int oth(int x){
return ((x-1)^1)+1;
}
struct edge{
int u,v; ll w,c; int nxt;
edge(){}
edge(int u_,int v_,ll w_,ll c_,int nxt_)
{ u=u_,v=v_,w=w_,c=c_,nxt=nxt_; }
}e[2*maxm];
int fst[maxn],tp=0;
void addedge(int u,int v,ll w,ll c){
e[++tp]=edge(u,v,w,c,fst[u]);
fst[u]=tp;
}
void addflow(int u,int v,ll w,ll c){
addedge(u,v,w,c);
addedge(v,u,0,-c);
}
ll dis[maxn],h[maxn],mxw[maxn];int cnt[maxn],frm[maxn],fre[maxn];
bool vis[maxn];
void spfa(){
static queue<int> q;
while(!q.empty()){ q.pop(); }
memset(dis,0x3f,sizeof(dis));
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
dis[s]=0;vis[s]=1;q.push(s);cnt[s]++;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
if(cnt[u]>n+1){
break;
}
for(int i=fst[u];i!=0;i=e[i].nxt){
int v=e[i].v;
ll c=e[i].c;
if(e[i].w==0){ continue; }
if(dis[v]>dis[u]+c){
dis[v]=dis[u]+c;
if(!vis[v]){ vis[v]=1;q.push(v);cnt[v]++; }
}
}
}
}
void clear(){
memset(cflow::fst,0,sizeof(cflow::fst));cflow::tp=0;
}
void init(int n_,int s_,int t_){
n=n_,s=s_,t=t_;
}
struct pr{
ll dis;int u;pr(){}pr(int u_,ll dis_){u=u_,dis=dis_;}
};
bool operator<(pr a,pr b){
return (a.dis!=b.dis)?(a.dis>b.dis):(a.u>b.u);
}
bool dijkstra(){
static priority_queue<pr> q;
while(!q.empty()){ q.pop(); }
memset(dis,0x3f,sizeof(dis));
dis[s]=0;mxw[s]=inf;q.push(pr(s,0));
while(!q.empty()){
int u=q.top().u;q.pop();
for(int i=fst[u];i!=0;i=e[i].nxt){
int v=e[i].v;
ll c=e[i].c+h[u]-h[v],w=e[i].w;
if(w && (dis[v]>dis[u]+c)){
dis[v]=dis[u]+c;
mxw[v]=min(mxw[u],w);
frm[v]=u;
fre[v]=i;
q.push(pr(v,dis[v]));
}
}
}
return dis[t]!=inf;
}
ll mincost,maxflow;
void MCMF(){
spfa();
memcpy(h,dis,sizeof(h));
mincost=maxflow=0;
while(dijkstra()){
ll flow=mxw[t];
maxflow+=flow;
mincost+=flow*(dis[t]-h[s]+h[t]);
for(int i=t;i!=s;i=frm[i]){
e[fre[i]].w-=flow;
e[oth(fre[i])].w+=flow;
}
for(int i=1;i<=n;i++){
h[i]+=dis[i]; // 敲重点，累加
}
}
}
}
int n,m,s,t;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
cflow::n=n; cflow::s=s; cflow::t=t;
for(int i=1;i<=m;i++){
int u,v;ll w,c;
scanf("%d%d%lld%lld",&u,&v,&w,&c);
if(c<0){
cflow::addflow(v,u,w,-c);
}else{
cflow::addflow(u,v,w,c);
}
}
cflow::MCMF();
printf("%lld %lld\n",cflow::maxflow,cflow::mincost);
return 0;
}
```