Posts tagged with MCMF


非常感谢这道题,准确的来说应该是这道题的数据。这道题其实是很简单的。 题意: 一堆箱子围成一个圈,每个箱子里面初始没有或有几个球。要求最后每个箱子里面最多一个球。每次转移球只能转移到相邻的箱子,转移一个球,需要花费1。问最小花费。 思路: 最暴力的思路是每个球对其他所有球都建立一条边,费用为最短距离。 但是有个显然的特点是,a -> b 与 a-> k , k->…

算是康复福利了,以前没做过,但是实际是非常水的题目,应该可以作为入门题了 诡异的是 这道题description莫名奇妙没了。 题意: 两个人从 1 -> n ,每条路径最多走两次,走第一次为 d ,走第二次为 d+a ,问最短的路径。 思路: 对于一组数据,建两次边即可。容量为1,花费分别为 d…

康复计划之 最小费用最大流 以前写的是直接在网上拿了一个模板,直接套了A…… 这次好好在纸上模拟了一下,理解了一下。 最小费用最大流的增广路算法简单说就是不断求最短路(因为残量网络和反向边的存在),记录最短路,再进行流量处理,直到最后不存在通路,则停止。 下面是一个 入门题 题意: 给你一张图,要你从1 -> n 再从 n -> 1…