苟且的狮子的博客

[CQOI2012]交换棋子

建图拆点，最小费用最大流题意：分析：首先我们认识到，对于我所在的棋盘，如果我把所有的黑子都摆放在指定的位置上了的话，那么白子也一定被摆在了指定的位置。所以，这里我们不妨只看黑子，考虑让其摆放在规定的黑子位置上所消耗的步数最小。不难想到，这是个匹配问题。我们要对所有的黑子对其归属位置进行匹...

Coding Contest

最小费用最大流，对数乘法换加法，浮点数比较题意：这道题看上去很裸，似乎就是一道最小费用流的题目。需要注意的有三点：1.这里面最小费用的计算是乘法，所以我们要对其取对数将其变为加法。2.因为e(u,v)的cost为浮点数，所以再spfa算法中我们便不能再直接比较了。需要加上个eps否则会一直超...

[SDOI2010]星际竞速

建图，网络流，最小费用最大流题意：分析：雨神说过，图论题难就难在建图上。这题我觉得建图还是蛮难的。我们捕捉一下重要信息：从一个额外的点出发，恰好经过每一个点一次，可以进行跳跃，永远是小点连大点。我们不难明白，所谓额外的点其实就是时空跳跃的中介点，也同时是起点。同时，我们也很本能的想将所...

Collect Jewel

最小费用最大流题意：分析：这是我第一次做最小费用最大流的题目。感觉还行，写个题解留作纪念。意识到这是个关于最小费用最大流问题并不难。但是，关键在于如何建图。拆点是一定的。我刚开始想，对每一个节点，拆成两个。原节点到拆点一条c=1 d=-vi 的路拆点到原节点一条c=inf,d=0的路。...