AC. 梦想

frank_c1

[BZOJ 1834] 网络扩容

发布于2016年03月20日 | 暂无评论 | 448阅读 | 费用流

题目描述

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

输入格式

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

N<=1000,M<=5000,K<=10

输出格式

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

题目解析

应该一看就能想到最小费用最大流,建模对我来说还是有一定难度。

第一问很简单,直接跑最大流即可。考虑第二问。扩容的实际意义是什么呢?我们花了费用得到了额外的流量。根据这个思想,可以这样建模:

1.在最大流的残留网络上建图,此时网络最大流应为0。

2.设超级源ss向1连容量为K,费用为0的边。(限制增加流)

3.对于原图每条边(u,v)uv连容量为无穷大,费用为w_i的边。(提供有偿流量)

跑最小费用最大流即可。这样网络最大流一定是K,对应题意中网络流量增加K的条件,又保证了增加的流量所产生的费用最小,满足题目要求。