【题解】星际转移问题 网络流24题

Prelude

传送到洛谷:→_→
传送到LOJ:←_←
这道题看着觉得特别复杂,不太会做,加上刚学网络流,对这些题没有什么思路。就这样,看了看WC2017讲义上的题解,大概知道思路了,后来还是不太会,又看了看别人的代码。。。

Solution

这题的解法是这样的。首先对于所有太空船能到达的太空站做一个并查集,来判断问题是否有解(网上也有很多当天数达到一定的时候就判断问题无解的,不太清楚怎么证明最大天数,而且这样个人认为比较慢吧。。。)。
建图是这样建的:把地球和太空站拆成每一天是一个点,月球是汇点。从源点向每一天的地球连一条容量为INF的边。然后把通过太空船从上一天在的太空站到这一天的当前的太空站也连一条容量为\(h[i]\)的边。由于人可以在地球、太空站上过若干天,所以把上一天的地球、太空站和这一天的它自己也连一条容量为INF的边。一天接着一天地连边,连完之后跑Dinic,看下最大流能增加多少,如果最大流的总量超过了\(k\),那么就说明到这一天人可以全部送往月球,就输出当前天数,终止程序。
(Ps:我一开始数组\(h\)和\(r\)开小了,没看到\(m\leq 20\),结果交上去\(m=20\)的点\(k\)的值从50变成了4,以后一定要看清楚数据范围,数组注意多开一点防止越界)
2018年的第一发提交就是这题了,90分,从去年做到今年。。。我其实交之前下了数据测的(逃),还改了改代码,然而Windows并不会越界,就没查出最后一个点的问题来。

Code

 

发表评论