第五十五章（1/2）

说是与非第五十五章：准备有声小说在线收听

x 第二天余文波上课的时候并没有表现出任何异样还是老样子他喜欢把事情都藏在心里不知道为啥我总感觉有些背脊发凉今天上午上课玩手机的人更多了果然冬令营又叫冬眠营很多学生纷纷开始掉线我看了看徐超还在认真的做笔记我也就没有分神接着听下去了。下午开始我就慢慢掉线了不得不说人外有人天外有天以前总觉得自己牛逼现在看来自己还是跟真正的冠军存在差距。

我抽了个空给恒子发了消息我跟她说了我也在北京参加冬令营恒子过了很久才回复我她说道：“我交了新的男朋友了！”

“是吗他对你好吗？”

“还不错。”

“有空大家一起聚一聚吧等我冬令营这边忙完。”

“好。”

不知道为什么听到恒子交了新的男朋友我的心里酸溜溜的我的心里总归还是想着恒子的吧。老黄跟老李倒也来看过我一次叮嘱我一个人一定要好好努力七天内一定要再上一个档次他们两个现在一直在帮周涛巩固信息学的东西。说起周涛我也是一肚子火。

晚上营员讨论的时候我看到徐超正跟周涛两个人坐在一起不知道在讨论什么我走上前去一看原来是个太空飞行计划的题目题目的大概意思是有n个实验要做,做掉奖励相应的钱,但是每个实验需要相应的仪器,每个仪器启动起来要相应的钱,安排使得赚钱最多。

我看周涛还在给徐超讲闭合图的概念的东西不免偷笑起来他肯定是以为徐超是个半吊子殊不知徐超现在的编程能力怕是我都有点招架不住了徐超看到我在一旁偷笑于是说道：“莫诚难道知道这个题目怎么解吗？”

“还行略知一二。”

“那你倒是说说看。”周涛不屑地说道。

“很明显这是一个二分图,每个实验向需要的仪器连有向边,实验的点权为正,仪器的点权为负,要求最大权闭合图。这是一个选或不选的问题,所以可以转化成最小割的模型把选的归为s集,不选的归为t集。但是要求获利最大最小割是最小,所以我们要换个角度,要求扣的钱最少,因为所有实验的前都加起来是一定的。在最小割中,如果把s到所有试验表示的点连一条容量为奖励的钱（a类弧）,所有仪器到t连一条容量为启动仪器的钱（b类弧）,如果把a类弧割掉了,那么对应的那个实验就归到了t集,也就是不做了,那么就会有损失。如果把b类弧割掉了,那么相应的那个仪器归到了s集,也就是有损失。所有最小割就是使得损失最少的方案……”

“最大权闭合图的通用解法：s到正权值的点连边,容量为其权值,负权值的点到t连边容量为其绝对值,然后原图中的边容量为inf,ans=所有正权和-最小割。”

“bingo！”我向徐超竖起了大拇指。