【学习笔记】dij 费用流 + 势能函数

dij 最大流最小费用算法

背景：众所周知 dij 算法是不能跑 负权图 的，但是通过一些 trick 可以转化为 正权图 。

适用条件：无负环图。

先来考虑初始边权 全为正 的情况

说白了用 点标 h[u] 的形式去将 w(u,v) 改为 h[u]-h[v]+w(u,v)

那么从 s 到 u 的路径长度恰好抵消。

考虑初始 h 函数均为 0

每次将点 u 的权改为到 u 的最短路径长度

显然转化后还是正权图（用最短路的三角不等式证）

注意代码里面写的是 h[u]+=dis[u] （这是一个递推构造的过程）

思考：如果初始有负边呢？

那么我们跑 spfa 求一个合法 h 函数即可。

注意这个最短路不等式在负权图下的仍然成立。（事实上只要没有负环都是成立的 233）

那么点标无所谓正负了

【模板】最小费用最大流

AC code:

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
const int M=2e5+5;
int n,m,s,t;
int tot=1,cap[M],to[M],nxt[M],head[M],cost[M];
int dis[N],flw[N],pre[N],vis[N];
int h[N];
void add(int u,int v,int w,int c) {
	tot++;
	cap[tot]=w,to[tot]=v,nxt[tot]=head[u],head[u]=tot,cost[tot]=c;
	tot++;
	cap[tot]=0,to[tot]=u,nxt[tot]=head[v],head[v]=tot,cost[tot]=-c;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
bool dij() {
	for(int i=1;i<=n;i++) {
		dis[i]=0x3f3f3f3f;
		vis[i]=0;
	}
	q.push(make_pair(0,s));
	flw[s]=0x3f3f3f3f;
	dis[s]=0;
	while(q.size()) {
		int u=q.top().second; q.pop();
		if(vis[u]) {
			continue;
		}
		vis[u]=1;
		for(int k=head[u];k;k=nxt[k]) {
			int v=to[k];
			if(cap[k]>0&&dis[v]>dis[u]+h[u]-h[v]+cost[k]) {
				dis[v]=dis[u]+h[u]-h[v]+cost[k];
				pre[v]=k;
				flw[v]=min(flw[u],cap[k]);
				q.push(make_pair(dis[v],v));
			} 
		}
	}
	return dis[t]!=0x3f3f3f3f;
}
pair<int,int> EK() {
	pair<int,int> tmp;
	while(dij()) {
		for(int i=1;i<=n;i++) {
			h[i]+=dis[i];
		}
		tmp.first+=flw[t];
		tmp.second+=flw[t]*h[t];
		int now=t;
		while(now!=s) {
			int k=pre[now];
			cap[k]-=flw[t];
			cap[k^1]+=flw[t];
			now=to[k^1];
		}
	}
	return tmp;
}
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);
	}
	pair<int,int> ans=EK();
	printf("%d %d",ans.first,ans.second);
}

practice ：[BJOI2012] 连连看

先转化成二分图，然后跑 spfa 求 h，然后跑 dij