苟且的狮子

题解

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1)

/ 注册

全部文章 / 题解（共6篇）

点阵

最大流，建图题意：分析：难点就在建图。我们不难这样想：将每一条边视作一个点，将每一个格子视作一个点。格子点拆成两个。然后这样建造：但是，这很明显不能满足约束条件。对于相邻的两个格点，如果他们相邻的边被选中时，两个格点的s-s1或者s2-ed都要减一，并且该边所代表的点再也不能走了！很明显我...

最大流网络流建图

2020-08-30

1 569

[CQOI2012]交换棋子

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

最小费用最大流思维建图

2020-08-18

4 827

小Y写文章

网络流，二分、二分图最大匹配题意：分析：这一题出的好啊！！！！正是我能力边缘的题目。有助于提升实力！！！我们需要插入m段广告，有n+1个空位我们可以插入。当插入时，我们整体得不流畅度可能会改变。当我们看到max() 时，我们就应该尝试用二分的思想取考虑一下，a1,a2,a3,a4当我们...

二分最大流网络流二分图最大匹配建图

2020-08-16

7 1243

[SDOI2010]星际竞速

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

最小费用最大流建图

2020-08-15

2 974

Car的旅行路线

建图，最短路题意：分析：没有什么难以思考的地方，关键就是建图，我们以每个机场为节点建图。成功建图后跑4次dijstra算法取得城市a到城市b的最小路径就行了。但是，在此题中建图这件事还真是挺大工程的。代码量巨大，烦死我了。代码如下： #include<iostream> #i...

最短路建图

2020-07-29

1 646

小雨坐地铁

分层图，建图，最短路题意：分析：首先来看看我当时的思路吧！我们很容易发现这是个最短路问题，但线路的存在很棘手。雨神说过，图论的难点在于建图！如果成功建图接下来就只是套板子了。那来看看我们如何建图。我上来也没有思路，后是从实际生活入手的。想象一下，我们在站点i我们可以坐1,2,3三路高铁，...

最短路分层图建图

2020-07-27

7 766