好久没写题解了啊···

题目大意：

给你一幅n个点的网络，先求出其1到n的最大流，每条弧还会有个属性\(cost_i\)，表示没扩容一个单位的费用，现在我们要求的就是扩容K个单位的最小费用

思路：

这是一道比较裸的网络流，第一问直接dinic就是了，重点就在于第二问。我们把第一问的残量网络继续利用，其中的每条弧的费用都是0，此时我们再在第\(i\)条弧的两端之间在建一条弧，弧的容量是\(INF\)，费用就是\(cost_i\)。这样我们固然可以保证费用正确，可是我们保证不了扩容了K，我们就可以建一个超级源点，连向1号点，容量为K，费用为0。在这个网络中最大流一定是满流，也就是K啊，此时的最小费用就是我们所要求的。

具体实现：

这就很简单了，一遍\(dinic\)，再一遍\(MCMF\)我们就可以了

代码如下

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int maxn=10001,maxm=50001,inf=0x7f7f7f7f;

int n,m,k,tot,next[maxm<<1],beg[maxm<<1],head[maxn],flow[maxm<<1],fflow[maxm<<1],last[maxn],pre[maxn],fl[maxn],nxt[maxm<<1],to[maxm<<1],ccost[maxm<<1],cost[maxm<<1],d[maxn],dep[maxn];

bool vis[maxn];

void addedge(int x,int y,int z,int co,int type){

    nxt[++tot]=head[x];

    head[x]=tot;

    to[tot]=y;

    beg[tot]=x;

    flow[tot]=z;

    fflow[tot]=type?z:0;

    cost[tot]=type?co:0;

    ccost[tot]=co;

}

bool bfs(){

    memset(dep,0,sizeof(dep));

    queue<int> q;

    q.push(1);

    dep[1]=1;

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=nxt[i]){

            int u=flow[i],v=to[i];

            if(u>0 and !dep[v]){

                dep[v]=dep[x]+1;

                q.push(v);

            }

        }

    }

    return dep[n];

}

int dfs(int x,int mini){

    if(x==n)return mini;

    for(int i=head[x];i;i=nxt[i]){

        int u=flow[i],v=to[i];

        if(u>0 and dep[v]==dep[x]+1){

            int dd=dfs(v,min(mini,u));

            if(dd>0){

                flow[i]-=dd;

                flow[i^1]+=dd;

                return dd;

            }

        }

    }

    return 0;

}

int dinic(){

    int ret=0;

    while(bfs()){

        int tmp=dfs(1,inf);

        while(tmp){

            ret+=tmp;

            tmp=dfs(1,inf);

        }

    }

    return ret;

}

bool spfa() {

    memset(d,0x7f,sizeof(d));

    memset(fl,0x7f,sizeof(fl));

    memset(vis,0,sizeof(vis));

    queue<int> q;

    q.push(n+1);

    vis[n+1]=1;

    d[n+1]=0;

    pre[n]=-1;

    while(!q.empty()) {

        int now=q.front();

        q.pop();

        for(int i=head[now];i;i=nxt[i]){

            int v=to[i];

            if(fflow[i]>0 and d[v]>d[now]+cost[i]){

                d[v]=d[now]+cost[i];

                pre[v]=now;

                last[v]=i;

                fl[v]=min(fl[now],fflow[i]);

                if(!vis[v]){

                    vis[v]=1;

                    q.push(v);

                }

            }

        }

        vis[now]=0;

    }

    return pre[n]!=-1;

}

int mcmf(){

    int ret=0;

    while (spfa()){

        int now=n;ret+=fl[n]*d[n];

        while (now!=n+1){

            fflow[last[now]]-=fl[n];

            fflow[last[now]^1]+=fl[n];

            now=pre[now];

        }

    }

    return ret;

}

void rebuild(){

	int cnt=tot;

	for(int i=2;i<=cnt;i+=2){

		fflow[i]=flow[i];

		fflow[i+1]=flow[i+1];

		addedge(beg[i],to[i],inf,ccost[i],1);

		addedge(to[i],beg[i],0,-ccost[i],1);

	}

}

int main(){

    scanf("%d%d%d",&n,&m,&k);

    addedge(n+1,1,k,0,1);

    for(int i=1;i<=m;i++){

        int a,b,c,d;

        scanf("%d%d%d%d",&a,&b,&c,&d);

        addedge(a,b,c,d,0);

        addedge(b,a,0,-d,0);

    }

    int ans1=dinic();

    rebuild();

    int ans2=mcmf();

    printf("%d %d\n",ans1,ans2);

    return 0;

}