题解：P7173 【模板】有负圈的费用流

· · 题解

题解：P7173 【模板】有负圈的费用流

题目描述

板子，有负环的费用流

思路

我们考虑使用上下界的思想+最小费用最大流解决负环问题。

先定义一条边的五元组表示法，我们令从 u 连到 v，下界为 l_i，上界为 r_i，代价为 w_i 的边叫做 (u,v,l_i,r_i,w_i)。

首先，对于一个源汇流变成无源汇流，显然的，只需要连 (t,s,-inf,inf,0) 即可。

考虑上下界的一种理解方式：每一个点流量不守恒，利用原图中可以增广的路径修复每一个点的流量守恒条件，这说明，只要不超过上下界，一开始的不满足流量守恒的图可以是任意流量的。

然后我们考虑先将所有 (u,v,w,co) 的边看作 (u,v,0,w,co)，变成上下界无源汇网络流。

明显的，没有流就是一组可行流，但是这样修复图中是有负环的，无法跑费用流。

但是，我们的原图是可以在上下界内随意赋值的，于是对于负数权值的边，我们干脆让它在原图中流满，那么修复图中就只会出现边权为正的边，这样修复图中就不会出现负环了。

然后此时考虑修复，找到可行流，然后再把刚刚加的 (s,t) 边删掉，那么这样我们就成功的消除了所有的负环，此时再根据题目条件跑所需要的流即可。此时也是在原来的修复图上跑，同时我们刚刚已经知晓修复图上没有负环，于是也可以跑费用流了。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
const int maxn=1e6+10;
const int maxv=1e4+10;
int head[maxn],to[maxn],w[maxn],c[maxn],nxt[maxn],cnt=1;
void add_edge(int u,int v,int da,int cost){
    to[++cnt]=v;
    w[cnt]=da;
    c[cnt]=cost;
    nxt[cnt]=head[u];
    head[u]=cnt;
} 
int dis[maxn],st[maxn],cur[maxn];
int n,m,s,t,s1,t1,qwq;
bool spfa(int begin,int end,int bnd){
    queue<int> q;
    memset(st,0,sizeof(st));
    memset(dis,0x3f,sizeof(dis));
    dis[begin]=0,st[begin]=true,cur[begin]=head[begin];
    q.push(begin);
    while(!q.empty()){
        int u=q.front();
        st[u]=false;
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            if(i>bnd) continue;
            int v=to[i];
            if(w[i]>0&&dis[v]>dis[u]+c[i]){
                dis[v]=dis[u]+c[i];
                cur[v]=head[v];
                if(!st[v]){
                    st[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return dis[end]!=inf;
}
int co;
int find(int u,int lim,int end,int bnd){
    if(u==end) return lim;
    int sum=0;
    st[u]=true;
    for(int i=cur[u];i&&sum<lim;i=nxt[i]){
        if(i>bnd) continue;
        cur[u]=i;
        int v=to[i];
        if(w[i]>0&&dis[v]==dis[u]+c[i]&&!st[v]){
            int flow=find(v,min(w[i],lim-sum),end,bnd);
            if(!flow) dis[v]=-1;
            w[i]-=flow,w[i^1]+=flow;
            co+=flow*c[i];
            sum+=flow;
        }
    }
    st[u]=false;
    return sum;
}
int dinic(int begin,int end,int bnd){
    int ans=0,sum;
    while(spfa(begin,end,bnd)) 
    while(sum=find(begin,inf,end,bnd)) 
    ans+=sum;
    return ans;
}
int into[maxv];
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    int a,b,c,d;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        if(d<0){
            add_edge(b,a,c,-d);
            add_edge(a,b,0,d);
            into[a]-=c,into[b]+=c;
            co+=c*d;
        }else{
            add_edge(a,b,c,d);
            add_edge(b,a,0,-d);
        }
    }
    add_edge(t,s,inf,0);
    add_edge(s,t,0,0);
    qwq=cnt;
    s1=n+1,t1=n+2; 
    for(int i=1;i<=n;i++){
        if(into[i]<0) add_edge(i,t1,-into[i],0),add_edge(t1,i,0,0);
        else if(into[i]>0) add_edge(s1,i,into[i],0),add_edge(i,s1,0,0);
    }
    dinic(s1,t1,inf);
    printf("%lld ",dinic(s,t,qwq));
    printf("%lld",co);
}