题面

给定一张有向图，每条边都有一个容量 $C$ 和一个扩容费用 $W$。这里扩容费用是指将容量扩大 $1$ 所需的费用。

求： 1、 在不扩容的情况下，$1$ 到 $N$ 的最大流； 2、 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。

题目链接

思路

第一问是一个裸的最大流。

对于第二问，考虑在每条边旁边加一条边，对于边 $(a,b)$，将原来的边费用设为 $0$，再加一条从 $a$ 到 $b$ 的边，费用为  $w$，流量无限。

这样流量流过额外的边时相当于扩容。

题目要求输出最大流在原先的基础上增加 $k$ 的扩容费用，所以我们要限制总流量：在 $n$ 后面额外开一个汇点 $n+1$，连接 $n$ 和 $n+1$，流量为第一问的答案 $ans$ 加上 $k$。从 $1$ 到 $n+1$ 的最小费用最大流的费用就是第二问的答案。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,m,k,last[200005],to[200005],nextt[200005],s[200005],t[200005],top=1,ans=0,cost=0;
long long d[200005];
long long v[200005];
struct path{
    long long from,edge;
};
path p[200005];
void add(int a,int b,int c,int d){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    t[top]=d;
    last[a]=top;
}
bool spfa(long long S,long long T){
    queue<long long> q;
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    memset(p,-1,sizeof(p));
    q.push(S);
    v[S]=1;
    d[S]=0;
    d[T]=2147483647;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        for (int i=last[now];i;i=nextt[i]){
            long long j=to[i];
            if (s[i]<=0){
                continue;
            }
            if (d[now]+t[i]<d[j]){
                d[j]=d[now]+t[i];
                p[j].from=now;
                p[j].edge=i;
                if (!v[j]){
                    q.push(j);
                    v[j]=1;
                }
            }
        }
        v[now]=0;
    }
    if (d[T]<2147483647){
        return 1;
    }else{
        return 0;
    }
}
void EK(long long S,long long T){
    while (spfa(S,T)){
        long long minn=2147483647;
        for (int i=T;i!=S;i=p[i].from){
            minn=min(minn,s[p[i].edge]);
        }
        ans+=minn;
        for (int i=T;i!=S;i=p[i].from){
            s[p[i].edge]-=minn;
            s[p[i].edge^1]+=minn;
        }
        cost+=minn*d[T];
    }
}
int main(){
    cin>>n>>m>>k;
    for (int i=1;i<=m;i++){
        int a,b,c,d;
        a=read();b=read();c=read();d=read();
        add(a,b,c,0);
        add(b,a,0,0);
        add(n+a,n+b,19260817,d);
        add(n+b,n+a,0,-d);
        add(n+a,n+b,c,0);
        add(n+b,n+a,0,0);
    }
    EK(1,n);
    cout<<ans<<" ";
    add(n*2,n*2+1,ans+k,0);
    add(n*2+1,n*2,0,0);
    ans=0;cost=0;
    EK(n+1,n*2+1);
    cout<<cost<<endl;
}