给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。

输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1

13 19
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

const int maxn=1010;

const int maxm=100000;

int n,m,K,S,T,cnt,sum,ans;

int dis[maxn],to[maxm],next[maxm],head[maxn],cost[maxm],flow[maxm],inq[maxn];

int ea[maxm],eb[maxm],ec[maxm],ed[maxm],re[maxn],rv[maxn];

queue<int> q;

void add(int a,int b,int c,int d)

{

	to[cnt]=b,flow[cnt]=c,cost[cnt]=d,next[cnt]=head[a],head[a]=cnt++;

	to[cnt]=a,flow[cnt]=0,cost[cnt]=-d,next[cnt]=head[b],head[b]=cnt++;

}

int bfs()

{

	while(!q.empty())	q.pop();

	memset(dis,0,sizeof(dis));

	int i,u;

	dis[S]=1,q.push(1);

	while(!q.empty())

	{

		u=q.front(),q.pop();

		for(i=head[u];i!=-1;i=next[i])

		{

			if(!dis[to[i]]&&flow[i])

			{

				dis[to[i]]=dis[u]+1;

				if(to[i]==T)	return 1;

				q.push(to[i]);

			}

		}

	}

	return 0;

}

int SPFA()

{

	while(!q.empty())	q.pop();

	memset(dis,0x3f,sizeof(dis));

	int i,u;

	dis[S]=0,q.push(S);

	while(!q.empty())

	{

		u=q.front(),q.pop(),inq[u]=0;

		for(i=head[u];i!=-1;i=next[i])

		{

			if(flow[i]&&dis[to[i]]>dis[u]+cost[i])

			{

				dis[to[i]]=dis[u]+cost[i];

				re[to[i]]=i,rv[to[i]]=u;

				if(!inq[to[i]])

				{

					inq[to[i]]=1;

					q.push(to[i]);

				}

			}

		}

	}

	return dis[T]<=(1<<29);

}

int dfs(int x,int mf)

{

	if(x==T)	return mf;

	int temp=mf,i,k;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(dis[to[i]]==dis[x]+1&&flow[i])

		{

			k=dfs(to[i],min(temp,flow[i]));

			if(!k)	dis[to[i]]=0;

			flow[i]-=k,flow[i^1]+=k,temp-=k;

			if(!temp)	break;

		}

	}

	return mf-temp;

}

int main()

{

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

	int i;

	memset(head,-1,sizeof(head));

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

	{

		scanf("%d%d%d%d",&ea[i],&eb[i],&ec[i],&ed[i]);

		add(ea[i],eb[i],ec[i],0);

	}

	S=1,T=n;

	while(bfs())	ans+=dfs(S,1<<30);

	printf("%d ",ans);

	for(i=1;i<=m;i++)	add(ea[i],eb[i],1<<30,ed[i]);

	add(T,T+1,K,0);

	ans=0,T++;

	while(SPFA())

	{

		int minn=1<<30;

		for(i=T;i!=1;i=rv[i])	minn=min(minn,flow[re[i]]);

		ans+=minn*dis[T];

		for(i=T;i!=1;i=rv[i])	flow[re[i]]-=minn,flow[re[i]^1]+=minn;

	}

	printf("%d\n",ans);

	return 0;

}