#3215. [ZJOI2010] 网络扩容

    ID: 3215 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图结构网络流2010各省省选浙江图的建立建图最大流费用流

[ZJOI2010] 网络扩容

题目描述

给定一张有向图,每条边都有一个容量 cc 和一个扩容费用 ww。这里扩容费用是指将容量扩大 11 所需的费用。求:

  1. 在不扩容的情况下,11nn 的最大流;
  2. 11nn 的最大流增加 kk 所需的最小扩容费用。

输入格式

第一行包含三个整数 n,m,kn,m,k,表示有向图的点数、边数以及所需要增加的流量。

接下来的 MM 行每行包含四个整数 u,v,c,wu,v,c,w,表示一条从uuvv,容量为 cc,扩容费用为 ww 的边。

输出格式

输出文件一行包含两个整数,分别表示问题 11 和问题 22 的答案。

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%30\% 的数据,保证 n100n\le 100
  • 对于 100%100\% 的数据,保证 1n1031\le n\le 10^31m5×1031\le m\le 5\times 10^31k101\le k\le 101u,vn1 \leq u, v \leq n