网络流，离散化 题意： 分析： 不妨先看看这一题：hdu3572可以先做这题会发现这两题几乎一摸一样不同之处在于：1.本题时间跨度大足足有100W,所以如果按照原先的思路我们是要对其离散化的2.本题中的肉串可以分成k块同时烤制3.本题中一种肉块有n个 我们要解决这三点。先从2，3开始：一块肉可以分为k块同时烤制，最为朴素的思想就是拆点。但是点数的增多会提高时间复杂度。事实上我们只要对边权k就行了。(肉串到时间的边)同样，同一种肉串有n个，我们也只要对边权n(肉串到时间的边)再对start到肉串的边*n就可以了！！可以画图理解，不是那么好解释。 下面是离散化：我们时间跨度为100w但是总共最...

kruskai，贪心 题意： 分析： 这一题我是由kruskai算法为突破口的。我们想想，对于一揽子的节点，我们要对他们进行并查集操作，将其合成k个集合。然后求集合间的最短距离。我们想 让这个最短距离尽量大！ 由kruskai算法作为突破口，我们不妨对所有的边按照其权值从小到大排序。边：共有n*n-n个，权值为距离。然后贪心的从距离最小的边开始进行合并，直到合成k个集合。也就是执行kruskai算法操作。最后，遍历剩下的边，找到最小距离。 为什么可以这样贪心呢？因为，我们最终是要形成k个集合的对吧。那么我们为什么不尽量用距离小的边去形成k个集合呢？如果我们对于一个距离为1的边放着不用，去用...

矩阵树 这题不错，又学到了一个知识点。欸嘿嘿。 题意： 分析： 我们来看这道题：首先，我们不妨把外面虚拟成一个点。那么问的就是，矩形中的所有点能否到达外面的点。 这时，我们想想。如果能都联通的话应该会是什么情况？ 首先肯定有一些点本来就联通。我们以虚构的最外面的点出发，进行深度优先搜索。肯定能将本来就来联通的点标记出来。成为一个连通块1 然后剩下没有搜索到的点有两种情况：1.他们与'.'联通，构成一个连通块，然后可能可以通过填充'.'来与连通块1联通。2.他们没有与'.'联通，也就是说这些点无法通过变数'.'来与连通块1联通。over了。 就这两种吧！那我们不妨把每个连通块都遍历出来好了。...

代码如下： #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int max_n = 2e5 + 100; const int mod = 1e9 + 7; int n, m; int used[max_n]; struct edge { int u, v, cost; }E[max_n]; vector<pii>...

dfs 题意： 分析： 深搜没学好啊！我们会发现，这其实就是一个判断图是否是二分图的过程！那么，我们已知，二分图是没有奇数环的。所以，我们可以断定，要不可以染色，要不有奇数环！ 染色部分容易，广搜深搜都可以，分深度奇偶染色即可。但是，要我们找环，就有点困难了。因为要是环，所以我们选择深搜，因为要打印出来，所以我们要记录他的父节点！ 代码如下： #include<iostream> using namespace std; const int max_n = 3e5 + 100; const int max_m = 3e5 + 100; int n, m; struct edge...

并查集 题意： 分析： 很简单，直接并查集。自己再改改，维护一个cnt[i]记录集合i中有多少个元素就可以了。 题解并不是我真正的目的，我真正的目的是： 我永远喜欢小木曾雪菜！！！！！！！！！ 代码如下： #include<iostream> #include<algorithm> using namespace std; const int max_n = 1e4 + 100; int n, m; int par[max_n]; int rak[max_n]; int cnt[max_n]; void init() { for (int i = 1;i...

二分图最大匹配，HK算法，暴力枚举 题意： 分析： 这道题是很明显是二分匹配题目。但因为我初学二分图所以刚开始并没有看出如何建立二分图的。我是想，对于人：1,2,3,4,5,6,7,8在刚开始匹配，1去将他手中的一个任务交给5然后到2开始交任务，如果2也有一个要交给5的任务，那么此时他发现5已经有任务了！所以，我们要看1，能不能将5的任务收回找别人交？ 其实，这就是一个寻找增广路的过程！！！所以，二分图的做法自然就出来了。我们建立二分图：1 12 23 34 45 5如上所示。 然后，算他的最大匹配就ok了。但是，要判断哪些点是必须不能去掉的点却好麻烦。。。我不会强连通分量，所以只能暴力枚举...

循环dp、spfa、松弛操作 题意： 分析： 其实，我标签里的所谓循环dp其实也就是类似分层图。不过是另一种角度看待问题而已。我认为对于状态相互转移的图论问题应该适用。 首先，让我们回顾一下Bellman-Ford算法。Bellman-Ford在试图解决最短路问题时总结了一个状态转移公式：d[i] = min(d[k] + cost[k,i] k为i的相邻节点) d[i] 为节点i到节点1的最短距离 我们很容易就能发现如果所给的图不是一个DAG的话，那么这个dp公式是会陷入死循环的！假设i和j构成一个环i需要j推出，j需要i推出。。。。。。 那么，Bellman-For...

二分图最大匹配 题意： 分析： 经典的求最大子集的问题。我们先求最大匹配。最大子集 = 总定点数 - 最大匹配选择你的算法，我选择HK算法！ 但是摆在我们面前的还有一个问题：如何区分图中顶点所在的集合？ 1.染色法：我们连完边建完图后，进行搜索，搜索深度为奇数的为一个子集，为偶数的为一个子集 2.观察法：对，我们不妨先在草稿纸上画画：这是我画的，我们很容易就发现当i+j为奇数是是一个子集，为偶数时是另一个子集。如此我们找到了划分的一句。接下来划分就可以了。 代码如下： #include<iostream> #include<algorithm> #include&l...

dp，斐波那契数列 题意： 分析： 我们现列举简单的例子：对第一个例子，he he zhou is watching you我们简写为： a a b c d e那么一共有几种呢？首先自己是一个然后我们两两交换：a (b a) c d e a a (c b) d e a a b (d c) e a a b c (d e)一共四种尝试交换更多：a (b a) (d c) e a (b a) c (d e) a a (c b) (e d)一共三种。总共八种！ 我们看上式似乎发现了什么，对开头的a a明显其中一个是多余的。那么我们不妨先考虑 a...

最短路，链式向前星，循环dp，分层图 题意： 分析： 这题不难，循环dp问题而已(分层图)正好最近我认真研究过，所以当时在赛场上的时候我还是很有自信能做出来的。 思路如下，我们添加一维构造循环dp。d[i][j]为节点i在j状态下距离s的最短距离！！！我们很容易能推出其动态转移方程：d[i][j] = min(d[k][j] k为i邻节点，且k与i同类型或者为M) min(d[k][(j+1)%2] k为i邻节点，且k与i类型相反或为M)二者取小 很容易的发现这是个典型的循环dp，我们使用松弛操作对其进行破解。使用dijstra具体原理请看我的另一篇博客：https://b...

最小生成树、kruskai算法 题意： 废话：做了些题单的题后，我发现题目考察点基本上围绕着 建图、算法本身理解、dp 三点展开。本题考察的是对kruskai算法的理解 分析： 我们首先抓住重要信息：公路1是一定比公路2开销大的！至少要有k条公路1.那么很明显我们就只铺设k条公路1好了，剩下的都铺设公路2！！这是个贪心。 那么问题来了，我们选取那些路铺设公路1呢？ 下面想想kruskai算法的原理：kruskai算法是求最小路的算法。假设我们有两个由点组成的树，我们要把这两个树连接在一起以形成一个树。我们只能依靠这两个树他们中节点相互链接的路径。kruskai指出，链接最短路是最优的。这样...

松弛操作，循环dp 题意： 分析： 又是这种题，很好，对于已经明白松弛操作与循环dp的我来说已经不成问题了。给出dp状态dp[i][j] 指在第j步到达节点i的最短路径d[i][j] = min(d[k][j-1] + edge(i,k) + cost[j] k为i相邻节点)这是个无限递归的循环dp关于循环dp https://blog.nowcoder.net/n/8316b13c345d49b08b2ae7f41c49da71##代码如下: #include<iostream> #include<algorithm> #include<qu...

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