学步园

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7fffffff 
using namespace std;
struct data{
    int from,to,next,v,cost,t;
}e[50001];
int n,m,k,cnt=1,head[1001],from[1001],q[1001],h[1001],dis[1001],ans;
bool inq[1001];
void insert(int u,int v,int w,int c){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].v=w;
    e[cnt].t=c;
    e[cnt].from=u;
    head[u]=cnt;
}
void ins(int u,int v,int w,int c){
    insert(u,v,w,c);
    insert(v,u,0,-c);
}
void _insert(int u,int v,int w,int c){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].v=w;
    e[cnt].cost=c;
    e[cnt].from=u;
    head[u]=cnt;
}
void _ins(int u,int v,int w,int c){
    _insert(u,v,w,c);
    _insert(v,u,0,-c);
}
bool bfs(){
    int t=0,w=1,i,now;q[t]=1;
    memset(h,-1,sizeof(h));h[1]=0;
    while(t<w){
        now=q[t++];i=head[now];
        while(i){
            if(e[i].v&&h[e[i].to]==-1){
                h[e[i].to]=h[now]+1;
                q[w++]=e[i].to;
            }
            i=e[i].next;
        }
    }
    if(h[n]==-1)return 0;
    else return -1;
}
int dfs(int x,int f){
    if(x==n)return f;
    int i=head[x],w,used=0;
    while(i){
        if(e[i].v>0&&h[e[i].to]==h[x]+1){
            w=f-used;
            w=dfs(e[i].to,min(e[i].v,w));
            e[i].v-=w;
            e[i^1].v+=w;
            used+=w;
            if(used==f)return f;
        }
        i=e[i].next;
    }
    if(!used)h[x]=-1;
    return used;
}
void dinic(){
    while(bfs())ans+=dfs(1,inf);
}
void build(){
    int t=cnt;
    for(int i=2;i<=t;i+=2)
        _ins(e[i].from,e[i].to,inf,e[i].t);
}
bool spfa(){
    int t=0,w=1,i,now;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    q[t]=dis[0]=0;inq[0]=1;
    while(t<w){
        now=q[t++];i=head[now];
        while(i){
            if(e[i].v>0&&dis[e[i].to]>dis[now]+e[i].cost){
                dis[e[i].to]=dis[now]+e[i].cost;
                from[e[i].to]=i;
                if(!inq[e[i].to]){
                    q[w++]=e[i].to;
                    inq[e[i].to]=1;
                }
            }
            i=e[i].next;
        }
        inq[now]=0;
    }
    if(dis[n]==inf)return 0;
    else return 1;
}
void mcf(){
    int i=from[n],x=inf;
    while(i){
        x=min(x,e[i].v);//寻找最小容量边 
        i=from[e[i].from];
    }
    i=from[n];
    while(i){
        e[i].v-=x;//路径上每条边容量减小x 
        e[i^1].v+=x;
        ans+=x*e[i].cost;//扩容
        i=from[e[i].from]; 
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int u,v,c,w;
        scanf("%d%d%d%d",&u,&v,&c,&w);
        ins(u,v,c,w);
    }
    dinic();
    printf("%d ",ans);
    ans=0;build();
    ins(0,1,k,0);
    while(spfa())mcf();
    printf("%d",ans);
    return 0;
}