Johnson 全源最短路算法
Floyd 可以 \(O(n^3)\) 处理全源最短路，Bellman-Ford 单源最短路的复杂度是 \(O(nm)\) 的，Dijkstra 可以做到 \(O(m\log m)\) 但不能处理负边权，所以 Johnson 全源最短路算法通过处理使得可以用 \(n\) 次 Dijkstra 解决有负权图的全源最短路。
先建超级源点，向各点连边权为 \(0\) 的有向边，跑一次 \(Bellman-Ford\)，得到最短路 \(h\)，将 \(h_u\) 作为 \(u\) 节点的势能，将 \(d(u,v)\) 改为 \(d'(u,v)=d(u,v)+h_u-h_v\)。
这样在最短路过程中，\(p_1\to p_2\to \cdots\to p_{n-1}\to p_{n}\)，最短路值应该是：
注意到之和两端点势能有关，所以按照这个方法去做是可以找到最短路的。
同时根据 \(h_u+d(u,v)\ge h_v\)，则 \(d(u,v)+h_u-h_v\ge 0\)，也就是一个正权图。
这样复杂度是 \(O(nm\log m)\)。
Primal-Dual 原始对偶算法
其实和上面类似，这个算法解决了不含负环的费用流，复杂度不再是 EK 的上界 \(O(nmf)\)，其实就是改变了求最短路的算法。
依旧是从源点 \(S\) 开始跑 Bellman-Ford 记录势能 \(h_u\)，边权改为 \(d(u,v)+h_u-h_v\)。
问题在每次增广之后增加并减少了一些边。
这里的解决方案是，每次跑完 Dijkstra，把势能 \(h_u\) 改为 \(h_u+dis_u\)，这显然能代表最短路，证明和上面一样，关键是对边权是否全为正的讨论。
证明也是类似的，在上一次跑 Dijkstra 时，原有的边 \((u,v)\) 有 \(dis_u+(d(u,v)+h_u-h_v)\ge dis_v\)，于是 \(d(u,v)+(h_u+dis_u)-(h_v+dis_v)\ge 0\)，而新增加的边则是一定在最短路上，于是 \(dis_u+(d(u,v)+h_u-h_v)=dis_v\)，进而 \(d(v,u)+(h_v+dis_v)-(h_u+dis_u)=0\)，边权非负。
这样就可以在 \(O(nm+m\log mf)\) 的复杂度内解决问题，如果图有特殊性质，第一次的 Bellman-Ford 可以换成 BFS 之类的。
点击查看代码
ll h[maxn];
bool vis[maxn];
inline void SPFA(){
queue<int> q;
memset(h,0x3f,sizeof(h));
q.push(S);
h[S]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].c;
if(e[i].lim&&h[u]+w<h[v]){
h[v]=min(h[v],h[u]+w);
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
struct node{
int u;
ll d;
node()=default;
node(int u_,ll d_):u(u_),d(d_){}
bool operator<(const node& rhs)const{
return d>rhs.d;
}
};
ll dis[maxn];
int pre[maxn];
inline void Dijkstra(){
priority_queue<node> q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(node(S,0));
dis[S]=0;
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
ll w=e[i].c+h[u]-h[v];
if(e[i].lim&&dis[u]+w<dis[v]){
dis[v]=dis[u]+w,pre[v]=i;
q.push(node(v,dis[v]));
}
}
}
}
inline ll mincost_maxflow(){
SPFA();
ll mincost=0;
while(1){
Dijkstra();
if(dis[T]==0x3f3f3f3f3f3f3f3f) return -mincost;
for(int u=1;u<=T;++u) h[u]+=dis[u];
int flow=inf;
for(int u=T;u!=S;u=e[pre[u]^1].to){
flow=min(flow,e[pre[u]].lim);
}
for(int u=T;u!=S;u=e[pre[u]^1].to){
mincost+=1ll*e[pre[u]].c*flow;
e[pre[u]].lim-=flow,e[pre[u]^1].lim+=flow;
}
}
}