P7173 【模板】有负圈费用流

Flanksy · 2023-07-13 22:48:21 · 题解

有源汇上下界最小费用可行流

为了消除负环，强制所有负权边 (x,y) 满流并统计这些负权边的费用。加入边 (y,x) 用于退流，其权值为边 (x,y) 权值的相反数，流量下界为 0，流量上界为 (x,y) 的容量，然后使用上下界网络流求解。不会上下界费用流的建议先去做 P4043。

强制满流可以解释为加入流量上界为 f，下界为 f，费用为 v 的边 (x,y)。注意到这时 (x,y) 只需要统计一下，不需要实际添加。而反向边实际上是用来退流反悔的。

更详细的解释可以看其他题解，现有题解都没有给出一个比较格式化的求解流程，这里补一个。

以下流程中部分是给没学过上下界网络流的读者看的，可能有些繁琐。

注意下文中提及的边的“容量”代表该边的流量下界为 0，流量上界为容量。

• 读入边的信息 x,y,f,v 并根据边权分类讨论：

• 建立附加源汇点 SS,TT 并连边，具体地，对于点 i：

• 加入容量为 inf 的边 (T,S)，在图上跑以 SS 为源点，TT 为汇点的最小费用最大流（求解有源汇最小费用可行流）。将可行流流量（最后加入的边 (T,S) 的流量）计入答案流量，将此次最小费用最大流的费用计入答案费用。

• 撤去所有与附加源汇点 SS,TT 相连的边和最后加入的边 (T,S)。跑一次以 S 为源点，T 为汇点的最小费用最大流。将此次最小费用最大流的流量和费用计入答案流量和答案费用。

刚开始的强制满流可以保证任意时刻网络无负环。

答案流量为可行流流量与最小费用最大流流量之和，答案费用为强制满流的费用、可行流的费用与最小费用最大流的费用之和。

总体时间复杂度 O(nmf)，其中 f 为求解过程中网络的最大流量。

#include<bits/stdc++.h>
using namespace std;
constexpr int inf=1000000000;
namespace net{
    int cnt,lim,h[205],hc[205],dis[205],f[100005],w[100005],to[100005],nxt[100005];
    bool on[205];
    queue<int> q;
    void lockstar(int x){lim=x;}//封锁下标大于 x 的边 
    void reset(){cnt=1,lim=inf;}
    inline void addstar(int x,int y,int _f,int _w){
        f[++cnt]=_f,w[cnt]=_w,to[cnt]=y,nxt[cnt]=h[x],h[x]=cnt;
        f[++cnt]=0,w[cnt]=-_w,to[cnt]=x,nxt[cnt]=h[y],h[y]=cnt;
    }
    bool SPFA(int x,int y){
        memset(dis,63,sizeof(dis)),dis[x]=0;
        for(q.push(x);!q.empty();q.pop()){
            int now=q.front();
            on[now]=0;
            for(int i=h[now];i;i=nxt[i]) if(i<=lim&&f[i]&&dis[to[i]]>dis[now]+w[i]){
                dis[to[i]]=dis[now]+w[i];
                if(!on[to[i]]) on[to[i]]=1,q.push(to[i]);
            }
        }
        return dis[y]<inf;
    }
    int dfs(int x,int flow,int aim){
        if(x==aim||!flow) return flow;
        int ret=0;
        on[x]=1;
        for(int &i=hc[x];i;i=nxt[i]) if(i<=lim&&!on[to[i]]&&dis[to[i]]==dis[x]+w[i]){
            int now=dfs(to[i],min(flow,f[i]),aim);
            ret+=now,f[i]-=now,f[i^1]+=now,flow-=now;
            if(!flow) break;
        }
        on[x]=0;
        return ret;
    }
    pair<int,int> SSP(int S,int T){
        pair<int,int> ret;
        while(SPFA(S,T)){
            memcpy(hc,h,sizeof(hc));
            int flow=dfs(S,inf,T);
            ret.first+=flow;
            ret.second+=dis[T]*flow;
        }
        return ret;
    }
}
//强制满流负权边 连反向正权边退流 限制退流流量
//有源汇上下界最小费用可行流解决
int n,m,S,T,SS,TT,ans,mem,maxflow,w[205];
int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    net::reset(); 
    for(int i=1;i<=m;i++){
        static int x,y,f,_w;
        scanf("%d%d%d%d",&x,&y,&f,&_w);
        if(!f) continue;//要你何用
        if(_w>=0) net::addstar(x,y,f,_w);
        else{//下界0 上界f 费用取反
            w[x]-=f,w[y]+=f,ans+=_w*f;
            net::addstar(y,x,f,-_w);
        }
    }
    SS=n+1,TT=SS+1,mem=net::cnt;
    for(int i=1;i<=n;i++){
        if(w[i]>0) net::addstar(SS,i,w[i],0);
        if(w[i]<0) net::addstar(i,TT,-w[i],0);
    }
    net::addstar(T,S,inf,0);
    auto SSP=net::SSP(SS,TT);//可行流
    maxflow=net::f[net::cnt];//拿到可行流实际流量
    ans+=SSP.second;//拿到可行流费用
    net::lockstar(mem);//封边
    SSP=net::SSP(S,T);//在原图上跑
    maxflow+=SSP.first,ans+=SSP.second;
    printf("%d %d\n",maxflow,ans);
    return 0;
}