苟且的狮子

分类

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

/ 注册

TA的专栏 88篇文章 0人订阅

kuangbin题单刷题详解(最短路篇)

9篇文章 696人学习

kuangbin题单刷题详解(网络流)

10篇文章 648人学习

kuangbin题单刷题详解(匹配问题)

14篇文章 724人学习

kuangbin刷题题单详解(后缀数组)

8篇文章 588人学习

kuangbin刷题题单详解(博弈论)

8篇文章 737人学习

kuangbin刷题题单详解(连通图)

9篇文章 814人学习

Kuangbin刷题详解(AC自动机)

4篇文章 613人学习

Kuangbin题单详解(kmpManacher)

20篇文章 950人学习

Kuangbin题单详解(区间dp)

6篇文章 791人学习

全部文章（共229篇）

方格取数(2) HDU - 1569

网络流，最大权独立点集题意： ##分析：看到这一题，我的第一反应是二分图求最大独立点集。想要用HK算法干掉他。但是仔细一看并非如此，题目让球的是最大权独立点集。这就是完全不同的问题了。真正的解法推荐看论文：胡伯涛《最小割模型在信息学竞赛中的应用》，直接跳到第五部分读就行了。不得不感叹，真是巧妙...

网络流最大点权独立集最小割

2020-08-14

1 900

kebab HDU - 2883

网络流，离散化题意：分析：不妨先看看这一题：hdu3572可以先做这题会发现这两题几乎一摸一样不同之处在于：1.本题时间跨度大足足有100W,所以如果按照原先的思路我们是要对其离散化的2.本题中的肉串可以分成k块同时烤制3.本题中一种肉块有n个我们要解决这三点。先从2，3开始：一块肉可以...

网络流离散化

2020-08-14

1 496

[JSOI2010]GROUP 部落划分 GROUP

kruskai，贪心题意：分析：这一题我是由kruskai算法为突破口的。我们想想，对于一揽子的节点，我们要对他们进行并查集操作，将其合成k个集合。然后求集合间的最短距离。我们想让这个最短距离尽量大！由kruskai算法作为突破口，我们不妨对所有的边按照其权值从小到大排序。边：共有n*...

kruskai 贪心

2020-08-09

4 659

白金元首与独舞

矩阵树这题不错，又学到了一个知识点。欸嘿嘿。题意：分析：我们来看这道题：首先，我们不妨把外面虚拟成一个点。那么问的就是，矩形中的所有点能否到达外面的点。这时，我们想想。如果能都联通的话应该会是什么情况？首先肯定有一些点本来就联通。我们以虚构的最外面的点出发，进行深度优先搜索。肯定能将...

dfs 矩阵树

2020-08-09

2 562

A Very Easy Graph Problem

代码如下： #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int>...

最小生成树

2020-08-08

1 574

Graph Coloring I

dfs 题意：分析：深搜没学好啊！我们会发现，这其实就是一个判断图是否是二分图的过程！那么，我们已知，二分图是没有奇数环的。所以，我们可以断定，要不可以染色，要不有奇数环！染色部分容易，广搜深搜都可以，分深度奇偶染色即可。但是，要我们找环，就有点困难了。因为要是环，所以我们选择深搜，因为要...

dfs 二分图

2020-08-02

2 681

白色相簿

并查集题意：分析：很简单，直接并查集。自己再改改，维护一个cnt[i]记录集合i中有多少个元素就可以了。题解并不是我真正的目的，我真正的目的是：我永远喜欢小木曾雪菜！！！！！！！！！代码如下： #include<iostream> #include<algorith...

并查集

2020-08-02

2 717

国政议事

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

二分图二分图最大匹配

2020-08-02

1 654

最优贸易

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

分层图循环dp

2020-08-02

3 713

[TJOI2013]攻击装置

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

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

2020-08-02

1 700