dijkstra 算法求费用流

众所周知，在求解费用流的时由于要建反边，必然会有负权边的存在。所以费用流的通常写法是 EK+SPFA。
事实上我们是可以通过一些技巧，使得 dijkstra 也可以跑费用流。这样的好处是保证了复杂度的下限。
本文将探讨如何使得 dijkstra 可以跑费用流。

dijkstra 算法不能处理负权边。所以我们首先要在边权上做文章。
给每个点 $u$ 构造一个势 $h_u$ ，满足 $\forall e_{u\rightarrow v}\in E,h_u-h_v+\text{val}_e\ge 0$ ，然后将 $\text{val'}_e$ 赋值为 $h_u-h_v+\text{val}_e\ge 0$ 。此时，原图中的边均非负，并且新图上的的最短路 $\mathcal{P'}_{u\rightarrow v}$ 一定是原图上的最短路 $\mathcal{P}_{u\rightarrow v}+h_u-h_v$ 。$h_u-h_v$ 是常量，所以我们依然可以求出最短路。

在最初的时候，由于只有正权边的容量非零，所以可以将初始时的 $h$ 设为全 $0$ 。

跑完一遍费用流后会使得一些边的反向边加入，此时需要更新 $h$ 数组。我们仅会加入最短路上的边，所以我们只考虑最短路上的边。对于最短路上的边 $u\rightarrow v$ ，有

$\text{dis}_u+\text{val}'_{u\rightarrow v}=\text{dis}_v\\ \text{dis}_u+h_u-\text{dis}_v-h_v+\text{val}_{u\rightarrow v}=0\\ \text{dis}_v+h_v-\text{dis}_u-h_u-\text{val}_{u\rightarrow v}=0$

又我们新增的边的性质

$\text{val}_{v\rightarrow u}=-\text{val}_{u\rightarrow v}$

所以当令 $h_u\leftarrow h_u+\text{dis}_u$ 时，$\text{val}'_{u\rightarrow v}=\text{val}'_{v\rightarrow u}=0$ ，满足了最短路上的边权非负的要求。并且容易证明，非最短路上的边的边权仍然非负。

贴份代码，题目是洛谷的 MCMF 模板。实测后发现怎么在随机图上跑得都比 SPFA 快？

const int N=1e4+5,M=2e5+5,INF=1e9;
using namespace std;
int head[N],nt[M],to[M],val[M],d[M];
int n,m,s,t,ans,cost,num=1;
struct node{
	int x,dis;
	bool operator <(const node &b)const{
		return dis>b.dis;
	}
};
priority_queue<node>q;
int h[N],pre[N],dis[N],incf[N],used[N];
bool BFS(){
	
	for(int i=1;i<=n;++i) dis[i]=INF,used[i]=0;
	q.push((node){s,0});dis[s]=0;incf[s]=INF;
	while(!q.empty()){
		int x=q.top().x;q.pop();
		if(used[x]) continue;
		used[x]=1;
		for(int i=head[x];i;i=nt[i]){
			int y=to[i],z=d[i]+h[x]-h[y];
			if(!val[i]) continue;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				incf[y]=min(incf[x],val[i]);
				pre[y]=i;
				q.push((node){y,dis[y]});
			}
		}
	}
	return dis[t]!=INF;
}
void update(){
	int x=t,y;
	while(x!=s)
		y=pre[x],val[y]-=incf[t],val[y^1]+=incf[t],x=to[y^1];
	ans+=incf[t];cost+=(dis[t]+h[t])*incf[t];
	for(int i=1;i<=n;++i) h[i]+=dis[i];
}
inline void Add(int x,int y,int z,int l){
	++num;nt[num]=head[x];head[x]=num;to[num]=y;val[num]=z;d[num]= l;
	++num;nt[num]=head[y];head[y]=num;to[num]=x;val[num]=0;d[num]=-l;
}
int main(){
	
	r(n),r(m),r(s),r(t);
	for(int i=1,x,y,z,l;i<=m;++i)
		r(x),r(y),r(z),r(l),Add(x,y,z,l);
	while(BFS()) update();
	printf("%d %d\n",ans,cost);
	return 0;
}