苟且的狮子

题解

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

/ 注册

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

国政议事

二分图最大匹配，HK算法，暴力枚举题意：分析：这道题是很明显是二分匹配题目。但因为我初学二分图所以刚开始并没有看出如何建立二分图的。我是想，对于人：1,2,3,4,5,6,7,8在刚开始匹配，1去将他手中的一个任务交给5然后到2开始交任务，如果2也有一个要交给5的任务，那么此时他发现5已经有...

二分图二分图最大匹配

2020-08-02

1 671

最优贸易

循环dp、spfa、松弛操作题意：分析：其实，我标签里的所谓循环dp其实也就是类似分层图。不过是另一种角度看待问题而已。我认为对于状态相互转移的图论问题应该适用。首先，让我们回顾一下Bellman-Ford算法。Bellman-Ford在试图解决最短路问题时总结了一个状态转移公式：d[i...

分层图循环dp

2020-08-02

3 734

[TJOI2013]攻击装置

二分图最大匹配题意：分析：经典的求最大子集的问题。我们先求最大匹配。最大子集 = 总定点数 - 最大匹配选择你的算法，我选择HK算法！但是摆在我们面前的还有一个问题：如何区分图中顶点所在的集合？ 1.染色法：我们连完边建完图后，进行搜索，搜索深度为奇数的为一个子集，为偶数的为一个子集 2...

二分图最大子集二分图图论二分图最大匹配

2020-08-02

1 709

[HNOI2006]公路修建问题

最小生成树、kruskai算法题意：废话：做了些题单的题后，我发现题目考察点基本上围绕着建图、算法本身理解、dp 三点展开。本题考察的是对kruskai算法的理解分析：我们首先抓住重要信息：公路1是一定比公路2开销大的！至少要有k条公路1.那么很明显我们就只铺设k条公路1好了，剩下的都...

最小生成树 kruskai

2020-07-29

1 642

追债之旅

松弛操作，循环dp 题意：分析：又是这种题，很好，对于已经明白松弛操作与循环dp的我来说已经不成问题了。给出dp状态dp[i][j] 指在第j步到达节点i的最短路径d[i][j] = min(d[k][j-1] + edge(i,k) + cost[j] k为i相邻节点)这是个无限...

Dijstra 循环dp Bellman-Ford

2020-07-29

2 695

Car的旅行路线

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

最短路建图

2020-07-29

1 646

Rinne Loves Graph

dp松弛问题(循环特性) 题意：分析： dp松弛问题。这是我的总结。所谓的最短路，不过是dp只不过该dp无法借由循环和记忆化搜索实现(因为有环使其左右横跳)详细见我的另一篇题解，正好是题单中的下一题：https://blog.nowcoder.net/n/8316b13c345d49b08b2...

Dijstra dp Bellman-Ford 循环dp

2020-07-28

6 676

Rinne Loves Dynamic Graph

Bellman-Ford算法，dijstra算法，循环dp问题这题很好，让我重新认识到了最短路到底是为解决了一个什么样的问题！！！！题意：分析：首先，我不会分层图！！！！所以，这题我主要是围绕dp展开。我们必须要知道题中所给函数1/(1-x)是个周期为三的周期函数那么边权就为x,1/(x...

Dijstra dp Bellman-Ford

2020-07-28

3 1004

小雨坐地铁

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

最短路分层图建图

2020-07-27

7 766

Forsaken喜欢独一无二的树

题意：分析：正如“jxnu-19-软技一班-刘晟”所说的，按照kruskai算法的想法来看的话，出现多条最短路径的原因只可能是存在复数的最小权值边连接着两个集合以供选择。那我们其实只要在kruskai算法进行的同时动手脚就行了。我们先对权值进行从小到大的排序，然后将其分为一个个的相等权值的集...

最小生成树 kruskai

2020-07-27

3 633