| 题目名称 | 1325. [ZJOI 2010] 网络扩容 |
|---|---|
| 输入输出 | networkzj2010.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 闫星光
于2013-03-28加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：77， 提交：132， 通过率：58.33% | ||||
|
刘睿佳 |
100 | 0.000 s | 0.00 MiB | C++ |
|
野 |
100 | 0.007 s | 0.00 MiB | C++ |
|
赵成钢 |
100 | 0.017 s | 4.32 MiB | C++ |
|
zys |
100 | 0.018 s | 0.90 MiB | C++ |
|
妖羽 |
100 | 0.019 s | 0.77 MiB | C++ |
|
ZXCVBNM_ |
100 | 0.020 s | 0.80 MiB | C++ |
|
ONCE AGA |
100 | 0.021 s | 6.44 MiB | C++ |
|
叉这这 |
100 | 0.022 s | 0.73 MiB | C++ |
|
Qw |
100 | 0.022 s | 19.40 MiB | C++ |
|
彭自涵 |
100 | 0.023 s | 0.72 MiB | C++ |
| 关于 网络扩容 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数据水到反向边花费忘置成负数也能过
 Hzoi_chairman
2016-11-06 07:15
4楼
| ||||
|
费用流第一题，来一发评论
| ||||
|
数组开小搞半天= =！
| ||||
|
通过这道题我知道了vector不能存太多东西尼玛。。
20000条边居然会爆。。RE到死。 然后COGS的答案判定好像不严格？我把答案输出在两行也算我过了 | ||||
问题描述
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：
1、 在不扩容的情况下，1到N的最大流；
2、 将1到N的最大流增加K所需的最小扩容费用。
输入数据 (network.in)
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。
接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
输出数据 (network.out)
输出文件一行包含两个整数，分别表示问题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