网络流瞎想

IMG_2229.JPG

请假想有一个原点和一个汇点。这样的网络流能干什么呢?

首先想到左边的点和右边的点可以分为早上和晚上,在左边的点连线代表从早上到另一个早上,右边的点之间的连线代表从一个晚上到另一个晚上,中间的点表明从早上待到晚上。然后就想到了时空机器。一些特定的时空机可以把你从某个早上传送到另一个早上,或者从某个晚上传送到另一个晚上,或者你可以在时空机外面从早上待到晚上,但不能从时空机外过夜。

这样就是,你一旦在时空机外从早上待到晚上,你就再也无法进入早上的时空机了。也就是你可以从某种状态进入另一种状态,但是不能再回来了。

就好像一堆士兵驻守某地区,左边的点代表他们坚守要塞,而右边的点代表他们焚烧要塞转为游击战,但右边的点不能回到左边的点,也就是他们不能从游击战回到坚守要塞状态了。这么想还挺悲壮。每两个点代表一天,不同天之间的连线代表士兵需要损失多少人,如果司令能大概估算出不同状态下不同日子士兵会损失的人数,求士兵最少会损失多少人。

或者又是那个酒香不怕巷子深的酒馆,制作优质的酒时每天赚的钱就是左边的点,老板可以选择在某个日子掺水,当天可以省下很大成本,相当于赚了一大笔钱,然后就到了右边的点就是掺水后的每天赚的钱。问老板在某个特定前最多可以赚多少钱?我不会告诉你这个老板之后会欠下2.5个亿,然后带着他小姨子跑了。

IMG_2231.JPG

对于右边这个,一想到跑路,就想到黑车司机宰客。

比如有一些城市,每个城市有一些地点,司机可以从一个城市的某个地点开向另一个城市的某个地点,但道路是单向的。开每条路都有一定距离,怎样在到达终点前开尽量多的路程,以便得到尽量多的路费?

这就是这个多列网络流的用法,但多列网络流和一列网络流并没有什么实质的区别。只是多列看起来一目了然。

当然假设还有这样的用法:考试有五个科目语文数学英语艺术体育,你并不知道哪个人哪个科目得了多少分,但你知道英语得了60分的人数学得了100分,艺术得了79分的人语文可能得59分或者78…给出足够这类的条件,求这次考试最低总分和最高总分是多少?

显然把每一列当成每个科目就行了,但是还有一个问题,假如给出的条件是得了英语60分的人数学得了80分,语文得了70分,上面显然就从起点到终点连不了一条完整的单向线了,不过这显然并不是网络流的范围。

IMG_2230左边这样的网络流又能干什么呢?

左边的点连了不止一条线到右边的点,但右边的点也连了不止一条线到左边的点。

于是我想到吃药。左边是疾病,右边是对付疾病所需要的药的种类,每类药需要一些钱。治疗一种疾病需要多种药,那么就从左边的点连到右边的点,但一种药服用后可能引发并发症,就从右边的点连向左边。如果有某种病的话,就从源点向左边的点连条线。问最少需要钱才能恰好治好所有的病?有瘟疫公司的赶脚。比如右边有个环钻手术,能缓解你左边的轻微头疼,但会导致左边严重感染和休克。有《瘟疫公司》的赶脚。

就是这样,左边的点要到汇点需要经过右边的点,但右边的点又会影响左边的点。上面说到的吃药其实有点像DEBUG,你修复好了一个bug,又会有999个bug冒出来。网络流24题中就有这样一种“软件补丁”。

假如是一些普通的连线,但最后选择点的时候,如果左侧被连上则选左侧的,右侧的没被连上才选右侧的,又可以来干什么呢?一直没搞懂为什么行列也可以这样求。

总之,例如可以左方为我方狙击手,而右方为敌方狙击手,我方狙击手可以干掉部分敌方狙击手,但一旦开枪就会暴露,最后会被无情干掉。你尽管有N个狙击手,但你最多只能损失M个,问怎样才能杀死尽可能多的敌方狙击手?最后输出我方剩余狙击手及敌方剩余狙击手。

对于那种有限制的网络流,也就是右边的点还要再分别连一层点的,我曾经在Collector`s Problem也就是Bob收集贴纸那儿做过,尽管想得很复杂并且一维数组能解决的用了二维数组解决,但这种构图仍然能解决不少问题。

比如左侧可以是一些货物,而右侧的有一些公司对这些货物有不同的需求,但这些公司属于不同的地区,每个地区对于某一货物最多只能接受一个上限。那么左侧为货物,中侧为公司,右侧为地区限制。

三角形,想到的是魏蜀吴三国。某些城池你可以进去做生意,获得不同的报酬,而某些地方需要缴纳过路费而无利益,每个城池都有东西两个城门,你只能从一个城门进,从另一个城门出,而不可反过来。某些城池的城门有直达另外城池的城门的一条路,但需要交过路费。每个城池你最多只能进去一次。这好像也没什么特别的地方,无非就是按照题目连城门了。

Leave a Reply