题目描述

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

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


补常州集训的坑ing

solution

最大流最小割定理以及最大权闭合子图

建图

  1. 对于每个实验,连一条从s到实验,边权为实验利益的边。
  2. 对于每个需要的仪器,连一条从实验到器材,边权为INF的边。
  3. 对于每个仪器,连一条从器材到t,边权为器材耗费的边。

这样割出来的图,只会割掉源点与实验或者仪器与汇点的一些边。

而实验与仪器的边,不会被割掉,因为设置成inf了

答案就是总价值-最小割

最后输出与源点同一集合的实验和仪器

 


3
说点什么

avatar
1 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
DefFrancisdhyTQL Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
dhyTQL
游客
dhyTQL

qwq 剧捞