【网络流24题-洛谷P2762 太空飞行计划问题】

传送门

太空飞行计划问题

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={I1,I2,…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

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

输入输出格式

输入格式:

第1行有2 个正整数m和n。m是实验数,n是仪器数。接下来的m 行,每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用;接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

输出格式:

第1 行是实验编号;第2行是仪器编号;最后一行是净收益。

输入输出样例

输入样例#1:

输出样例#1:

说明

感谢@FlierKing 提供spj

n,m<=50

这道题数据是在windows生成的,输入数据中所有的换行都是’\r\n’而不是’\n’

 

建图挺巧妙的一道题。建立超级源点\(S\)与超级汇点\(T\),\(S\)向每个实验连一条有向边,边容量为该实验的赞助费用;每个仪器向\(T\)连一条有向边,边容量为该仪器的使用费用。然后对于每个实验,向每个需要使用的仪器连一条容量为无穷大的有向边。那么最优价值就是全部赞助费\(sum\)减去最大流\(maxflow\)。

证明:容易看出,如果从某个仪器到\(T\)的边满流了,则代表要选这个仪器。

那么对于实验呢?正好相反。如果\(S\)到某个实验满流了,相当于投入它的资金,全部从租用仪器费用那里“流出”了,这种情况下如果租用的仪器到\(T\)满流,代表刚好赞助费\(=\)租用费,否则赞助费\(<\)租用费,因此,无论如何这个实验都是不赚钱的。相反,如果\(S\)到某个实验没满流,相当于做完这个实验后还有“盈余”,因而选这个实验做肯定是好的。

再来说说为什么用最大流来跑。首先,我们知道,最大流=最小割,最小割中的边一定都是满流边。本题中,中间那些容量为无穷大的边不可能满流,肯定不在最小割中;其次,我们可以看出,最小割中的边,如果连接的是仪器和\(T\),由上述分析可知,该仪器要选;如果连接的是\(S\)与实验,由上述分析可知,该实验不选。

因此,最小割集中的点=不该选的实验+该选的仪器,而割集权值则为:不该选的实验的总费用+最佳方案的仪器的总费用,我们将割集权值记为\(Cut\)。

不该选的实验的总费用\(=\)全部实验总费用\(Sum\)-该选的实验的总费用。

我们需要的是该选的实验总费用\(-\)最佳方案的仪器总费用,联立上面的式子可以发现实际上这个目标函数就是\(Sum-Cut\),由于\(Sum\)是定值,因此只需\(Cut\)最小,则最后盈利就越多,而\(Cut\)最小就是最小割,也就是求最大流了。

最后,所选择的仪器和实验,就是最后一次增广时从\(S\)能访问到的点。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*