苟且的狮子
苟且的狮子
全部文章
题解
2020多校(6)
CF(27)
作业(3)
区域赛真题题解(提升思维!!!)(8)
寒假模拟赛(1)
未归档(1)
苏州大学排位赛(7)
随笔(1)
归档
标签
去牛客网
登录
/
注册
苟且的狮子的博客
人一我百、人百我万!
全部文章
/ 题解
(共6篇)
点阵
最大流,建图 题意: 分析: 难点就在建图。我们不难这样想:将每一条边视作一个点,将每一个格子视作一个点。格子点拆成两个。然后这样建造:但是,这很明显不能满足约束条件。对于相邻的两个格点,如果他们相邻的边被选中时,两个格点的s-s1或者s2-ed都要减一,并且该边所代表的点再也不能走了!很明显我...
最大流
网络流
建图
2020-08-30
1
558
[CQOI2012]交换棋子
建图拆点,最小费用最大流 题意: 分析: 首先我们认识到,对于我所在的棋盘,如果我把所有的黑子都摆放在指定的位置上了的话,那么白子也一定被摆在了指定的位置。所以,这里我们不妨只看黑子,考虑让其摆放在规定的黑子位置上所消耗的步数最小。 不难想到,这是个匹配问题。我们要对所有的黑子对其归属位置进行匹...
最小费用最大流
思维
建图
2020-08-18
4
811
小Y写文章
网络流,二分、二分图最大匹配 题意: 分析: 这一题出的好啊!!!!正是我能力边缘的题目。有助于提升实力!!! 我们需要插入m段广告,有n+1个空位我们可以插入。当插入时,我们整体得不流畅度可能会改变。 当我们看到max() 时,我们就应该尝试用二分的思想取考虑一下,a1,a2,a3,a4当我们...
二分
最大流
网络流
二分图最大匹配
建图
2020-08-16
7
1232
[SDOI2010]星际竞速
建图,网络流,最小费用最大流 题意: 分析: 雨神说过,图论题难就难在建图上。这题我觉得建图还是蛮难的。 我们捕捉一下重要信息:从一个额外的点出发,恰好经过每一个点一次,可以进行跳跃,永远是小点连大点。 我们不难明白,所谓额外的点其实就是时空跳跃的中介点,也同时是起点。同时,我们也很本能的想将所...
最小费用最大流
建图
2020-08-15
2
968
Car的旅行路线
建图,最短路 题意: 分析: 没有什么难以思考的地方,关键就是建图,我们以每个机场为节点建图。成功建图后跑4次dijstra算法取得城市a到城市b的最小路径就行了。但是,在此题中建图这件事还真是挺大工程的。代码量巨大,烦死我了。 代码如下: #include<iostream> #i...
最短路
建图
2020-07-29
1
649
小雨坐地铁
分层图,建图,最短路 题意: 分析: 首先来看看我当时的思路吧! 我们很容易发现这是个最短路问题,但线路的存在很棘手。雨神说过,图论的难点在于建图!如果成功建图接下来就只是套板子了。那来看看我们如何建图。我上来也没有思路,后是从实际生活入手的。想象一下,我们在站点i我们可以坐1,2,3三路高铁,...
最短路
分层图
建图
2020-07-27
7
745