#P1834. [ZJOI2010]network 网络扩容

    ID: 856 传统题 1000ms 64MiB 尝试: 4172 已通过: 1682 难度: 7 上传者: 标签>CF2200提高+/省选-Dinic残量网络指定流量最小费用流势能优化费用流Dijkstra费用流

[ZJOI2010]network 网络扩容

[ZJOI2010] 网络扩容

题目描述

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

  1. 在不扩容的情况下,11 到 nn 的最大流;

  2. 将 11 到 nn 的最大流增加 kk 所需的最小扩容费用。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

13 19

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 n≤100n\le 100。
  • 对于 100%100\% 的数据,保证 2≤n≤1032\le n\le 10^3,1≤m≤5×1031\le m\le 5\times 10^3,1≤k≤101\le k\le 10,1≤u,v≤n1\le u,v\le n,1≤c,w≤1001\le c,w\le100。

本站数据保证有向图中存在一条从 11 到 nn 的路径。可以在原有边上增加任意非负整数的容量,因而总能增加 kk 单位最大流。重边按不同的边处理。

同题资料