题目大意

给定一张$n$个点$m$条边的有向图，每条边都有一个容量$c$和一个扩容费用$w$（这里扩容费用是指将容量扩大$1$所需的费用）

询问

1. 在不扩容的情况下，$1$到$n$的最大流

2. 将$1$到$n$的最大流增加$k$所需的最小扩容费用

数据范围

$n\leqslant 1000，m\leqslant 5000，k\leqslant 10$

题解

做的第一题费用流，打个标记

第一个询问考察最大流（不多解释），第二个询问考察费用流

由于要增加$k$流量，因此在跑完最大流的残余网络继续建图

建一个超级源点，从超级源到$1$建一条容量为$k$，费用为0的边

为了一定能够使得最大流增加$k$，新建的其他边容量要到$+∞$

在残余网络上的每一条边建一条容量为$+∞$，费用为$w$的边，反向弧容量为$0$，费用为$-w$

对这个新图跑一遍最小费用最大流

1. 跑一遍最短路，确定费用最短的路径，并记录

2. 根据记录的最短路，根据容量最小边，检查是否可以增广

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,k,et=1,ans;
int u[5050],v[5050],c[5050],w[5050];
struct edge{int from,to,next,c,w;}e[100050];
int last[1050],d[1050],dis[1050],inq[1050],from[1050];
inline void addedge(int u,int v,int c,int w){
    e[++et]=(edge){u,v,last[u],c,w};last[u]=et;
    e[++et]=(edge){v,u,last[v],0,-w};last[v]=et;
}


inline bool bfs(){
    memset(d,-1,sizeof(d));
    queue <int> q;q.push(1);d[1]=0;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h){
            if (d[e[i].to]==-1 && e[i].c){
                d[e[i].to]=d[h]+1;
                q.push(e[i].to);
            }
        }
    }
    return d[n]!=-1;
}
int dinic(int x,int flow){
    if (x==n) return flow;int a,used=0;
    goedge(i,x)
        if (d[e[i].to]==d[x]+1 && e[i].c){
            a=dinic(e[i].to,min(flow-used,e[i].c));
            e[i].c-=a,e[i^1].c+=a,used+=a;
            if (used==flow) return flow;
        }
    if (!used) d[x]=-1;
    return used;
}

inline bool spfa(){
    For(i,0,n) dis[i]=inf;
    queue <int> q;
    q.push(0);dis[0]=0,inq[0]=1;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h)
            if (e[i].c && dis[h]+e[i].w<dis[e[i].to]){
                dis[e[i].to]=dis[h]+e[i].w;
                from[e[i].to]=i;
                if (!inq[e[i].to]){
                    q.push(e[i].to);
                    inq[e[i].to]=1;
                }
            }
        inq[h]=0;
    }
    return dis[n]!=inf;
}
inline void mcf(){
    int i=from[n],x=inf;
    while (i){
        x=min(x,e[i].c);
        i=from[e[i].from];
    }
    i=from[n];
    while (i){
        e[i].c-=x;
        e[i^1].c+=x;
        ans+=x*e[i].w;
        i=from[e[i].from];
    }
}

int main(){
    n=read(),m=read(),k=read();
    For(i,1,m){
        u[i]=read(),v[i]=read(),c[i]=read(),w[i]=read();
        addedge(u[i],v[i],c[i],0);
    }
    while (bfs()) ans+=dinic(1,inf);
    printf("%d ",ans);ans=0;

    For(i,1,m) addedge(u[i],v[i],inf,w[i]);
    e[++et]=(edge){0,1,last[0],k,0};last[0]=et;
    while (spfa()) mcf();
    printf("%d\n",ans);
    return 0;
}