基于 Dijkstra 的费用流算法

· · Algo. & Theory

众所周知，Dijkstra 不可以处理有负权的图，若我们在跑 Dijkstra 前，对每条边的权值做一些处理，就可以使用 Dijkstra 了，单轮的时间复杂度降到 \mathcal{O}((n+m)\log n)。

设一条边 (u,v) 的边权为 w(u,v)，一开始图为 G。

考虑给每个点一个权值 h_u，我们的目的就是要使得对于一条边 (u,v)，满足 w(u,v)'=w(u,v)+h_u-h_v\ge 0，那么就可以满足使用 Dijkstra，且最后的最短路径一定是原最短路径 +h_s-h_t。

不妨设 h_u=d_u，其中 d_u 表示 s\to u 的最短路，一开始用 SPFA 求解。

由于 d_v\le d_u+w(u,v)，那么 w'(u,v)=w(u,v)+d_u-d_v\ge 0，由此得到一个新图 G'。就可以在 G' 上跑 Dijkstra 了。

考虑一次增广完后，对于满足 d_u+w+h_u-h_v=d_v，即在最短路上的边 (u,v)，可能会产生一条反边 (v,u)，且边权为 -w，我们需要更新 h，使得其对新的边也成立，由于 -w-d_u-h_u+h_v+d_v=-w+(h_v+d_v)-(h_u+d_u)=0，不妨直接设 h_u\to h_u+d_u，显然此时不会影响正常的边，因为其余边满足 d_u+w+h_u-h_v\ge d_v，即 w+(d_u+h_u)-(d_v+h_v)\ge 0。

由于一般一开始都没有负权边，可以直接跑 Dijkstra，即不用求解 h_u。但若初始有负权边，那么要先跑一次 SPFA。

code：（【模板】最小费用最大流）

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=5e3+5,INF=0x3f3f3f3f3f3f3f3f;
struct edge{
    int to,nt,c,w;
}a[N<<5];
int head[N],at=1,h[N],d[N],vis[N],n,s,t,pre[N],m;
void add(int u,int v,int c,int w){
    a[++at]=(edge){v,head[u],c,w};
    head[u]=at;
}
void link(int u,int v,int c,int w){
    add(u,v,c,w);
    add(v,u,0,-w);
}
void dij(){
    for(int i=1;i<=n;i++)d[i]=INF;
    int flow=0,cost=0;
    while(1){
        priority_queue<pii> q;
        d[s]=0;q.push(m_p(0,s));
        while(!q.empty()){
            int u=q.top().se;q.pop();
            if(vis[u])continue;vis[u]=1;
            for(int i=head[u];i;i=a[i].nt){
                int v=a[i].to,c=a[i].c,w=a[i].w+h[u]-h[v];
                if(c&&d[v]>d[u]+w){
                    d[v]=d[u]+w,pre[v]=i;
                    q.push(m_p(-d[v],v));
                }
            }
        }
        if(d[t]==INF) break;
        int res=INF;
        for(int i=t;i!=s;i=a[pre[i]^1].to) res=min(res,a[pre[i]].c);
        flow+=res;
        for(int i=t;i!=s;i=a[pre[i]^1].to) a[pre[i]].c-=res,a[pre[i]^1].c+=res,cost+=res*a[pre[i]].w;
        for(int i=1;i<=n;i++) h[i]=min(INF,h[i]+d[i]),d[i]=INF,vis[i]=0;
    }
    printf("%lld %lld\n",flow,cost);
}
signed main(){
    n=rd(),m=rd(),s=rd(),t=rd();
    for(int i=1;i<=m;i++){
        int u=rd(),v=rd(),c=rd(),w=rd();
        link(u,v,c,w);
    }
    dij();
    return 0;
}