苟且的狮子
苟且的狮子
全部文章
题解
2020多校(6)
CF(27)
作业(3)
区域赛真题题解(提升思维!!!)(8)
寒假模拟赛(1)
未归档(1)
苏州大学排位赛(7)
随笔(1)
归档
标签
去牛客网
登录
/
注册
苟且的狮子的博客
人一我百、人百我万!
全部文章
/ 题解
(共4篇)
[CQOI2012]交换棋子
建图拆点,最小费用最大流 题意: 分析: 首先我们认识到,对于我所在的棋盘,如果我把所有的黑子都摆放在指定的位置上了的话,那么白子也一定被摆在了指定的位置。所以,这里我们不妨只看黑子,考虑让其摆放在规定的黑子位置上所消耗的步数最小。 不难想到,这是个匹配问题。我们要对所有的黑子对其归属位置进行匹...
最小费用最大流
思维
建图
2020-08-18
4
827
Coding Contest
最小费用最大流,对数乘法换加法,浮点数比较 题意: 这道题看上去很裸,似乎就是一道最小费用流的题目。需要注意的有三点:1.这里面最小费用的计算是乘法,所以我们要对其取对数将其变为加法。2.因为e(u,v)的cost为浮点数,所以再spfa算法中我们便不能再直接比较了。需要加上个eps否则会一直超...
最小费用最大流
对数乘法换加法
浮点数比较
2020-08-17
1
604
[SDOI2010]星际竞速
建图,网络流,最小费用最大流 题意: 分析: 雨神说过,图论题难就难在建图上。这题我觉得建图还是蛮难的。 我们捕捉一下重要信息:从一个额外的点出发,恰好经过每一个点一次,可以进行跳跃,永远是小点连大点。 我们不难明白,所谓额外的点其实就是时空跳跃的中介点,也同时是起点。同时,我们也很本能的想将所...
最小费用最大流
建图
2020-08-15
2
974
Collect Jewel
最小费用最大流 题意: 分析: 这是我第一次做最小费用最大流的题目。感觉还行,写个题解留作纪念。 意识到这是个关于最小费用最大流问题并不难。但是,关键在于如何建图。拆点是一定的。我刚开始想,对每一个节点,拆成两个。原节点到拆点一条c=1 d=-vi 的路拆点到原节点一条c=inf,d=0的路。...
最小费用最大流
2020-08-15
1
589