dijkstra + 势函数 费用流

dijkstra因为不能处理负权最短路，所以不能用来费用流的增广。

但是如果我们利用Johnson的思想，加一个势函数，把负变正，就能跑费用流了。

维护势函数也很简单，每次跑完dijkstra之后，对于最短路非INF的点，令势函数加上最短路即可。

dijkstra跑增广时直接把 w[i] -> w[i] + h[u] - h[v] ，对于u到v的边。

三种费用流比较：

EK+spfa：简单好写，速度慢。
EK+势函数的dijkstra：对于边多的情况很快。
ZKW：稠密图+流量大+费用小的情况比较快。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5010,M=2e5+10;
int n,m,s,t,h[N],d[N],v[N],e[N],res,maxflow;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d);	ade(b,a,0,-d);}
inline int dijkstra(){
	memset(d,0x3f,sizeof d);	d[s]=0;	int vis[N]={0};
	priority_queue<pair<int,int> > q;	q.push({0,s});
	while(q.size()){
		int u=q.top().second;	q.pop();
		if(vis[u])	continue;	vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]+h[u]-h[to[i]]){
				d[to[i]]=d[u]+w[i]+h[u]-h[to[i]];
				v[to[i]]=u; e[to[i]]=i;	q.push({-d[to[i]],to[i]});
			}
		}
	}
	for(int i=1;i<=n;i++)	if(d[i]<inf)	h[i]+=d[i];
	return d[t]<inf;
}
void EK(){
	while(dijkstra()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=h[t]*mi,maxflow+=mi;
	}
}
signed main(){
	cin>>n>>m>>s>>t;
	for(int i=1,a,b,c,d;i<=m;i++)	scanf("%d %d %d %d",&a,&b,&c,&d),add(a,b,c,d);
	EK();	cout<<maxflow<<' '<<res<<endl;
	return 0;
}