「网络流 24 题」太空飞行计划-最大权闭合子图

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E = \{ E_1, E_2, \cdots, E_m \}$ ,和进行这些实验需要使用的全部仪器的集合 $I = \{ I_1, I_2, \cdots, I_n \}$ 。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subseteq I$ 。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

「NOI2006」最大获利-网络流-最大权闭合子图

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后,公司得到了一共 $N$ 个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第 $i$ 个通讯中转站需要的成本为 $P_i$ 。

另外公司调查得出了所有期望中的用户群,一共 $M$ 个。关于第 i 个用户群的信息概括为 $A_i$ , $B_i$ 和 $C_i$ :这些用户会使用中转站 $A_i$ 和中转站 $B_i$ 进行通讯,公司可以获益 $C_i$​ 。

THU 集团的 CS&T 公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×