# 最小费用最大流算法总结

while(!que.empty())
{
int now=que.front();que.pop();vis[now]=0;
for (int i=st[now];~i;i=e[i].next)
if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost)
{
dis[e[i].to]=dis[now]+e[i].cost;
pe[e[i].to]=i,pv[e[i].to]=now;
if (!vis[e[i].to])
vis[e[i].to]=1,que.push(e[i].to);
}
}

while(spfa(S,T))
{
flow=INF;
for (int i=T;i!=S;i=pv[i])
flow=min(flow,e[pe[i]].flow);
COST+=flow*dis[T];
FLOW+=flow;
for (int i=T;i!=S;i=pv[i])
e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
}

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 2001000
#define N 1001000
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
e[++tot].to=y;
e[tot].from=x;
e[tot].flow=z;
e[tot].cost=zz;
e[tot].next=st[x];
st[x]=tot;
}
queue<int>que;
bool spfa(int S,int T)
{
memset(dis,0x33,sizeof dis);
memset(vis,0,sizeof vis);
que.push(S),vis[S]=1,dis[S]=0;
while(!que.empty())
{
int now=que.front();que.pop();vis[now]=0;
for (int i=st[now];~i;i=e[i].next)
if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost)
{
dis[e[i].to]=dis[now]+e[i].cost;
pe[e[i].to]=i,pv[e[i].to]=now;
if (!vis[e[i].to])
vis[e[i].to]=1,que.push(e[i].to);
}
}
return dis[T]<INF;
}
Pair mfmc(int S,int T)
{
int COST=0,FLOW=0,flow;
while(spfa(S,T))
{
flow=INF;
for (int i=T;i!=S;i=pv[i])
flow=min(flow,e[pe[i]].flow);
COST+=flow*dis[T];
FLOW+=flow;
for (int i=T;i!=S;i=pv[i])
e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
}
return make_pair(FLOW,COST);
}
main()
{
int m,from,to;
scanf("%d%d%d%d",&n,&m,&from,&to);
memset(e,-1,sizeof e);
memset(st,-1,sizeof st);
int S=from,T=to;
for(int i=0;i<m;i++)
{
int u,v,flow,cost;
scanf("%d%d%d%d",&u,&v,&flow,&cost);
}
Pair ans=mfmc(S,T);
printf("%d %d\n",ans.first,ans.second);
}

$$G’$$中的一条路径 $$p[1], p[2],\cdots, p[m]$$ 的权值为

\begin{align*}
w'[path]&=w'[p[1]][p[2]] + w'[p[2]][p[3]] + \cdots + w'[p[m-1]][p[m]]\\
&=h[p[1]]-h[p[2]] + w[p[1]][p[2]]\\
&+h[p[2]]-h[p[3]] + w[p[2]][p[3]]\\
&+\cdots\\
&+h[p[m-1]]-h[p[m]] + w[p[m-1]][p[m]]\\
&=w[p[1]][p[2]] + w[p[2]][p[3]] + \cdots + w[p[m-1]][p[m]] + h[p[1]]-h[p[m]] \\
&=w[path] + h[p[1]]-h[p[m]]
\end{align*}

\begin{align*}
d'[i] + w'[i][j] = d'[j]
\\d'[i] + w[i][j] + h[i]-h[j] = d'[j]
\d'[j] + h[j])-(d'[i] + h[i])-w[i][j] = 0 \\(d'[j] + h[j])-(d'[i] + h[i]) + w[j][i] = 0 \end{align*} (因为是费用流,所以有w[i][j] = -w[j][i]) 因此让所有\(h[i] += d'[i]后,新加入的边(j, i)也会满足势函数的性质。

\begin{align*}
d'[i] + w'[i][j] – d'[j] >= 0\\
d'[i] + h[i] – h[j] + w[i][j] – d'[j] >= 0\\
(d'[i] + h[i]) – (d'[j] + h[j]) + w[i][j] >= 0\\
\end{align*}

>S1 初始化h[]
>S2 在残留网络中做Dijkstra
>S3 若S到T有可行路径,则修改增广路上的边的容量并所有h[i] += d'[i],转S2,否则退出

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 2001000
#define N 1001000
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
struct node
{
int from,to,next,flow,cost;
}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
void add(int x,int y,int z,int zz)
{
e[++tot].to=y;
e[tot].from=x;
e[tot].flow=z;
e[tot].cost=zz;
e[tot].next=st[x];
st[x]=tot;
}
Pair main_pro(int s,int t)
{
static int h[N];
int flow=0,cost=0;
while(1)
{
static int dis[N],pv[N],pe[N];
memset(dis,0x33,sizeof dis);    //距离初始化为inf
dis[s]=0;
priority_queue<Pair,vector<Pair>,greater<Pair> >que;
que.push(Pair(0,s));
while(!que.empty())
{
Pair now=que.top();
que.pop();
if (now.first!=dis[now.second]) continue;
//dis[now.second]是目前的值，now.first是入堆时的值，如果目前的优，直接continue
if (now.second==t) break;
for (int i=st[now.second];~i;i=e[i].next)
{
int nowcost=e[i].cost+h[now.second]-h[e[i].to];
//现在的费用为这条路径的费用+起始点的势函数-结尾点的势函数
if (e[i].flow>0 && dis[e[i].to]>dis[now.second]+nowcost) //松弛
{
dis[e[i].to]=dis[now.second]+nowcost;
que.push(Pair(dis[e[i].to],e[i].to));
pv[e[i].to]=now.second; //更新节点所对应的路径
pe[e[i].to]=i;
}
}
}
if (dis[t]==INF)  //没有增广到T
break;
for (int i=0;i<n;i++)  //更新势函数
h[i]=min(h[i]+dis[i],INF);
int newflow=INF;
for (int x=t;x!=s;x=pv[x])  //找到最小流量
newflow=min(newflow,e[pe[x]].flow);
flow+=newflow;
cost+=newflow*h[t];
for (int x=t;x!=s;x=pv[x])  //更新流量
e[pe[x]].flow-=newflow,e[pe[x]^1].flow+=newflow;
}
return make_pair(flow,cost);
}

int main()
{
int m,from,to;
scanf("%d%d%d%d",&n,&m,&from,&to);
memset(e,-1,sizeof e);
memset(st,-1,sizeof st);
for(int i=0;i<m;i++)
{
int u,v,flow,cost;
scanf("%d%d%d%d",&u,&v,&flow,&cost);
}
Pair ans=main_pro(from,to);
printf("%d %d\n",ans.first,ans.second);
}