最大权闭合子图。
源点与实验连边权为实验费用的有向边;
仪器与汇点连边权为仪器费用的有向边;
实验与仪器之间连边权为 INF 的有向边。
答案为所有与源点相连的边的边权和减去图的最小割。
证明见国集队员胡伯涛论文 《最小割模型在信息学竞赛中的应用》 。
输出路径时,最后一次层次图中:
与源点相连的点即选做的实验;与汇点相连的点即选用的仪器。
注意
· 读入数据时,读到空格继续,否则停止。
· 仪器部分的点权 + 50,避免两部点权相同。
来源: http://www.bubuko.com/infodetail-2439213.html