[BZOJ1497/Luogu4174][NOI2006]最大获利(网络流)

发布于 2018-04-17  10 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1497/Luogu4174][NOI2006]最大获利(网络流)

Description

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后,公司得到了一共N个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。另外公司调查得出了所有期望中的用户群,一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci:这些用户会使用中转站Ai和中转站Bi进行通讯,公司可以获益Ci。(1≤i≤M, 1≤Ai, Bi≤N) THU集团的CS&T公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)

Tag

网络流

解决思路

把所有收益加起来,将最大获利转化为最小损失。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1497/Luogu4174][NOI2006]最大获利(网络流)


HNCJ OIer 一枚