首页 > 代码库 > 【网络流问题·我就想建好模】

【网络流问题·我就想建好模】

·列出一些以做的题目,来积累网络流建模型经验。

 

[1]星际转移问题

·特色:你不知道是在哪一天可以使全部人到达月球。

(误区:二分答案。不是这样做,因为最大流随时都处于最优解状态,所以我们只需要轻轻地枚举天数【T++】)

·建图思路:

(1)创建源点汇点,即地球和月球。

(2)飞船从地球接人,在月球放人,所以把在此位置的飞船与源点(汇点)建边。

(3)飞船昨天的状态,今天的飞船继承,这两个飞船之间建边。

(4)昨天空间站里面可能会有人,所以还要让昨天停靠在那里的飞船将他们运走(早运晚运,早晚都要运,这不影响最优决策)

SUM-UP:

      在常规的建图上,这道题使得图富有动态感。这个叫做“分层图”,但为了方便理解,在这道题中我们可以看做是根据实际情况不断加边的图。

额外提醒:每条边的容量cap怎么规定呢?除了(4)中的容量为h[i]外,其余都可以设为INF(或许从地球出发时容量应限制为k,但是每一天都在判断,这一点变得无关紧要)。为什么?因为(4)操作代表了实际情况下飞船的运输情况,然而其他的操作实际上是逻辑讨论规定的(比如说(3)号情况,你总不可能让飞船上的人经过一天就卡死一部分吧?所以用INF是得当的)

技术分享

n(太空站个数),m(太空船个数)和k(需要运送的地球上的人的个数)

【网络流问题·我就想建好模】