[BZOJ2324][ZJOI2011]营救皮卡丘(网络流,最短路)

发布于 2018-03-25  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2324][ZJOI2011]营救皮卡丘(网络流,最短路)

Description

皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。
火箭队一共有N个据点,据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为0号据点,一开始K个人都在0号点。
由于火箭队的重重布防,要想摧毁K号据点,必须按照顺序先摧毁1到K-1号据点,并且,如果K-1号据点没有被摧毁,由于防御的连锁性,小智一行任何一个人进入据点K,都会被发现,并产生严重后果。因此,在K-1号据点被摧毁之前,任何人是不能够经过K号据点的。
为了简化问题,我们忽略战斗环节,小智一行任何一个人经过K号据点即认为K号据点被摧毁。被摧毁的据点依然是可以被经过的。
K个人是可以分头行动的,只要有任何一个人在K-1号据点被摧毁之后,经过K号据点,K号据点就被摧毁了。显然的,只要N号据点被摧毁,皮卡丘就得救了。
野外的道路是不安全的,因此小智一行希望在摧毁N号据点救出皮卡丘的同时,使得K个人所经过的道路的长度总和最少。
请你帮助小智设计一个最佳的营救方案吧!

Tag

网络流,二分图

解决思路

如果是DAG,那么问题就是求一个费用最小的用K条不相交,可以用拆点的方式解决。但是这里是可能有环的无向图,并且还要求必须先经过标号小的点才能经过标号大的点。
从标号小的走到标号大的?这似乎构成了DAG。我们先考虑一个人怎么走,他一定是依次沿着最短路从小标号走到大标号,并且从u->u+1时不会经过大于u+1的点。这个可以用Floyed最短路预处理出来。
至于多个人的话,其实与一个人是一样的,每一个人都只能向标号更大的地方走。(当然,中间可能经过标号小的,但每一阶段结束的时候一定是走到标号更大的)
所以我们把原图转化为一个只从标号小的走到标号大的的DAG,然后考虑在这个DAG上求覆盖所有点的最短的K条链。
对于每一个点拆成两个点分别叫做入点和出点,记作u和u',从u到汇点连容量为1,费用为0的边,表示需要到达这个点;再从源点向u'连容量为1费用为0的边。第二条边可以看作是补充第一条边流走的流量的,你可以认为两条边是流量流入汇点再从源点流出,由于原图是连通的一定存在解,所以这样是对的。
再对于新DAG中的一条从小标号走到大标号的边u->v,连边u'->v,容量无穷,费用为其距离。
最后由于有K个人,所以从源点向0号点的出点连一条容量为K费用为0的边,你可以当做0的入点没有用。
然后在这个图上求最小费用最大流就可以得到最优解了。
为了方便处理,在代码中,我把每一个但点的标号都加了一,这样就不需要考虑0了。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2324][ZJOI2011]营救皮卡丘(网络流,最短路)


HNCJ OIer 一枚