- 博客(1025)
- 收藏
- 关注
RSS订阅
原创 最短路小结
模版和算法详解Floyd BellmanFord Dijkstra模型1.Floyd算法的变形：因为Floyd算法的核心是动态规划，所以三层for的功能是很强大的UVA-10048（两点之间的最长边达到最小） UVA-125 （两点之间的路径数量） UVA-104 （floyd的三层表示） HDU-4034 （floyd的变形）
2015-11-10 21:03:29
711
原创 二分图小结
概念 最小点覆盖 = 最大匹配数最大独立集 = n - 最大匹配数模版 二分图最佳完美匹配-KM算法二分图匹配-Hungary算法二分图多重匹配题目 POJ - 1466 Girls and Boys 最大独立集POJ - 1719 Shooting Contest 最大匹配POJ - 2594 Treasure Exploration 建模POJ - 3041 Astero
2015-09-14 21:17:15
615
原创 LCA小结
概念 算法ST算法(在线)#include #include const int MAXNODE = 100010;const int MAXEDGE = 200010;struct Edge { int u, v, next; Edge() {} Edge(int u, int v, int next): u(u), v(v), next(next
2015-09-13 21:29:45
574
原创 图论--欧拉路，欧拉回路(小结)
在题目中在慢慢细说概念 1.HDU - 3018 Ant Trip 题目大意：又N个村庄，M条道路，问需要走几次才能将所有的路遍历解题思路：这题问的是有关欧拉路的判定 欧拉路就是每条边只能走一次，且要遍历所有的边，简单的说就是一笔画(图连通) 这道题是无向图的欧拉路，无向图的欧拉路的判定:所有点的度数都是偶数度，或者只有两个点的度是奇数度，且图要是连通图知道欧拉路是什么后，这题就比较好做了，
2015-07-27 01:08:39
1658
原创 状态压缩题目小结
因为这是对题目的小结，所以写的时候比较随意（因为之前已经写过相应的博客了） 如果需要详细的解题报告，我的博客都有，当然每道题的后面也有相应题目的解析链接。 如果后续还有的话，会补上的1.POJ - 3254 Corn Fields 题目大意：有一个n*m的草地(草地上有的是沼泽)，现在要分配牛去上面吃草，要求每头牛不能相邻（不能有公共边），问有多少种分配方案，一头牛都不分配也算一种分配方案解题
2015-07-24 12:21:51
1556
原创 数位DP小结
如果以下错的地方，谢谢提出。1.HDU - 2089 不要62解题思路：这题的限制条件是不能出现4，和数字中不能包含62，那么就对这两个进行特判即可#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define N 12int n, m;int dp[N][N];int data[N];/
2015-07-23 23:14:30
916
原创 二分题目总结
在UVA上搜索二分时搜到了一个很好的public专题1.POJ - 3258 River Hopscotch http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16277解题思路:http://blog.csdn.net/l123012013048/article/details/45646911 这题是符合条件的情况下，解有
2015-05-13 17:52:39
984
原创 汉诺塔题目总结
参考了别人的代码的总结1.四柱汉诺塔问题和n柱汉诺塔问题 题目：#include<cstdio>#include<algorithm>#include<cmath>using namespace std;double f[70];void init() { f[1] = 1; f[2] = 3; for(int i = 3; i <= 65; i++) {
2015-04-25 22:41:35
2170
原创 UVA - 111 History Grading 最长公共子序列
题目大意：给出n个序列，求出每个序列和第一个序列的最长公共子序列的长度(从第二个序列开始算起)解题思路：这题要注意的是所给数组的表示方式，如 4 1 2 3，表示1要放在第四位，2要放在第一位，以此类推，所以正确的顺序应该是2 3 4 1，这道题目算是模版题目了。#include <cstdio>#include <cstring>#include <string>using namespac
2018-01-01 01:03:53
463
原创 网络流小结
对这段时间做的网络流问题做一个小结，希望有用网络流算法的模版和详解 EK算法 ISAP Dinic MCMF模型和建模1.多源多汇问题：源有多个，汇也有多个，流可以从任意一个源流出，最终可以流向任意一个汇，总流量等于所有源流出的总流量，也等于流进所有汇的总流量建模方式：加一个超级源s’和超级汇t’，然后从s’向每个源引出一条有向弧，容量为无穷大，每个汇向t’引一条有向弧，容
2015-11-11 22:42:30
1221
1
原创 LightOJ - 1254 Prison Break(最短路＋大剪枝)
题目大意：给你每个加油站加一升油需要的费用和一张地图。 现在有Q个询问，询问的是当车的油箱容量为C时，从S到T所需要花费的最少钱解题思路：还是多维最短路，用dp[i][j]表示到达i点时，油箱里还剩有j升油时的最小花费，这里有一个剪枝，就是如果到达那边时，费用比上次到达时还大的话，就不用更新后面的了 这里用的是Dijkstra，所以只要走到终点了，不管油箱还有多少油，都表示最小费用了#inclu
2015-11-10 21:17:54
1246
原创 LightOJ - 1281 New Traffic System(二维最短路)
题目大意：给你N个点，M条已有的边，K条可以添加的边，K条中最多只能选择D条，问0到N－1的最短路解题思路：二维最短路，多开一维存储走到该点已经选择了多少条边了#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int N = 10010;cons
2015-11-10 21:13:31
959
原创 LightOJ - 1174 Commandos(floyd)
题目大意：给你N个点，M个人(M>N)，要求这些人同时从点S出发，走到点T，其间M个人要经过所有的点，问需要的最短时间解题思路：floyd求出 S到任意点的距离和任意点到T的距离，接着找出最大的dp[S][i] + dp[i][T]即可#include <cstdio>#include <cstring>#include <algorithm>using namespace std;cons
2015-11-10 21:11:13
695
原创 LightOJ - 1316 A Wedding Party(最短路+状态压缩)
题目大意：有N个点，M条有向边，S个特殊点。现在要求你从0走到N-1,经过的特殊点的数量最多，且走过的路径最小解题思路：刚开始开了一个dp[N][1 << S]的数组，可想而知，MLE了 后面想想，只需要处理出(开始点，特殊点，终点)这些点之间的距离，再用状态压缩去做就好了#include <cstdio>#include <cstring>#include <algorithm>#incl
2015-11-10 21:08:00
847
原创 LightOJ - 1099 Not the Best(次短路)
题目大意：找出点1和点n的次短路解题思路：变成2维记录，一个记录最短路，一个记录次短路即可#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int M = 100010;const int N = 5010;const int INF = 0x
2015-11-10 00:15:15
555
原创 LightOJ - 1019 Brush (V)(floyd)
题目大意：求第一点和最后一点的最短距离解题思路：100的量，floyd搞起#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 110;const int INF = 0x3f3f3f3f;int dis[N][N];int n, m, cas = 1;void
2015-11-10 00:13:33
549
原创 LightOJ - 1417 Forwarding Emails(强连通+dfs)
题目大意：你有一个秘密，但你只能告诉一个。这个人如果有认识的人的话，他就会把你的秘密告诉出去，这样就一传十，十传百了。现在你想要知道，最多能有多少人知道解题思路：同一个连通分量内的人都是可知的，所以缩点，然后连边，从入度为0的点出发，dfs找出所能到的最远处，在dfs过程中统计一下有多少个人知道#include <cstdio>#include <cstring>#include <algori
2015-11-10 00:12:29
754
原创 LightOJ - 1210 Efficient Traffic System(强连通)
题目大意：给出一张有向图，问需要添加多少条边，才能使该有向图变成强连通图解题思路：强连通，缩点，算出每点的入度和出度，找出max（入度为0，出度为0），这个就是答案 解释一下为什么，如果要强连通的话，就得让所有点都有入度和出度，所以添加的边的数量就是max(入度为0，出度为0)#include <cstdio>#include <cstring>#include <algorithm>usin
2015-11-10 00:09:04
721
原创 LightOJ - 1034 Hit the Light Switches(强连通)
题目大意：有N盏灯，灯满足u, v要求，表示u亮了，v也就亮了 问需要开几盏灯，才能让所有的灯都亮了解题思路：强连通块内的灯能相互作用。求出强连通块，然后缩点连边，找出入度为0的点，入度为0的点，就是要按的灯的数量#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N =
2015-11-10 00:05:52
973
原创 LightOJ - 1003 Drunk(拓扑排序判环)
题目大意：问所给的边中，有没有出现环解题思路：拓扑排序判环了#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <map>#include <string>#include <queue>using namespace std;const int N = 10010;st
2015-11-10 00:02:48
899
原创 LightOJ - 1221 Travel Company(负环)
题目大意：给你N个点，M条边，每条边有相应的 in和out，现在公司要求，找到一个环，使得这个环内的边的in / out > p解题思路：将式子变形，环内的in / out > p，就变成了 0 > 环内的out * p - 环的in，就相当于找到一个负环了#include <cstdio>#include <cstring>#include <queue>using namespace st
2015-11-10 00:01:23
627
原创 LightOJ - 1108 Instant View of Big Bang(负环)
题目大意：给你一张带权图，问从哪几点出发，可以走到-INF解题思路：能走到负环的点都可以，现在的问题是，怎么找出这些点 正面不好思考的话，换一下反面，环的性质，一个负环存在的话，把他所有的边的方向都取反，那么那个负环还是存在的既然边可以反向，那么走到负环的边，就变成了负环能到达的边了，这样就比较好求了#include <cstdio>#include <cstring>#include <al
2015-11-09 23:57:53
1134
原创 LightOJ - 1074 Extended Traffic(负环)
题目大意：给出每个点的权值和边，假设边为(u, v)，那么该边的权值就是(val[v] - val[u]) ^ 3 问从点1出发，到达所给点的最短路解题思路：有可能会出现负环，出现负环的话，就将负环内的点所能到达的所有点都标记一下#include <cstdio>#include <cstring>#include <queue>using namespace std;const int
2015-11-09 23:54:49
779
原创 LightOJ - 1256 Word Puzzle(欧拉路)
题目大意：给你N个单词，问这些单词能否首尾相连解题思路：能首尾相连的话，就会形成一条欧拉路了 有向图的欧拉路的要求： 1.连通 2.要么全部的点的入度 = 出度，要么仅有两个点的入度 != 出度，其中一个点入度 - 出度 ＝1,另一个点出度-入度=1，其他的点都是入度=出度就这样判断是否形成欧拉路 输出的话，就用fluery算法了#include <cstdio>#include <cst
2015-11-09 23:51:43
672
原创 LightOJ - 1086 Jogging Trails（欧拉+状态压缩）
题目大意：有一个人要跑完所有的路，且要跑的路程最短，问如何跑解题思路：跑完所有的路，且要跑的路程最短，跑欧拉路肯定是最短的。但是给出的图有可能不是欧拉回路，所以得自己再拼凑一下 无向图的欧拉回路就是所有点的度都是偶数了，所以找出所有度为奇数的点，状压求解连接这些点的最短路#include <cstdio>#include <cstring>#include <algorithm>using
2015-11-09 23:48:19
827
原创 LightOJ - 1094 Farthest Nodes in a Tree(树的直径)
题目大意：给你一棵树，问树上两个结点的最远距离解题思路：先用0做根结点，找出最远的叶子结点。再已该叶子结点做根结点，就能找到最远的距离了#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int N = 30010;struct Edge{
2015-11-08 23:02:10
576
原创 LightOJ - 1039 A Toy Company(BFS)
题目大意：给你三个字符，字符可以向下变化或者向上变化，再给出几个限制，问需要变化几次才能变成最终串解题思路：BFS裸题#include <cstdio>#include <cstring>#include <queue>using namespace std;const int N = 30;const int M = 100;struct Node { int x, y, z,
2015-11-08 23:00:15
1449
原创 LightOJ - 1012 Guilty Prince(DFS)
题目大意：给你一张地图，起始位置是‘@‘，空地是’.’，障碍是’#’，问能遍历多少个’.’解题思路：dfs裸题#include <cstdio>#include <cstring>#include <queue>using namespace std;const int N = 30;struct Node { int x, y; Node() {} Node(int
2015-11-08 22:58:54
709
原创 POJ - 2019 Cornfields(二维RMQ)
题目大意：中文题意解题思路：二维RMQ 用dp[row][col][i]表示[row, col]和[row + 2 ^ i, col + 2 ^ i]所围成的矩阵的最值#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 260;int n, b, q;int Mi
2015-11-08 22:55:57
418
转载 01分数规划
摘自http://blog.csdn.net/hhaile/article/details/8883652 因为当前只看了01分数规划，所以后面的就没拷贝过来了，想看的可以自己点链接 【关键字】 0/1分数规划、最优比率生成树、最优比率环 【背景】 根据楼教主的回忆录，他曾经在某一场比赛中秒掉了一道最优比率生成树问题，导致很多人跟风失败，最终悲剧。可见最优比率生成树是多么凶残的东西，但是
2015-11-08 18:18:09
521
转载 最长上升子序列
转自：http://blog.csdn.net/dangwenliang/article/details/5728363 稍有改动这题目是经典的DP题目，也可叫作LIS（Longest Increasing Subsequence）最长上升子序列 或者 最长不下降子序列。很基础的题目，有两种算法，复杂度分别为O(n*logn)和O(n^2) 。A.O(n^2)算法分析如下： （a[1]…a[n]
2015-11-08 16:32:49
407
转载 最长公共子序列
转自http://blog.csdn.net/v_july_v/article/details/6695482第一节、问题描述 什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：
2015-11-08 15:24:42
481
转载 二维树状数组详解
以下摘自http://www.java3z.com/cwbwebhome/article/article1/1369.html?id=4804当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组. 通常对一维数组最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.而树状数组的修改和查询均可在O(log(n))的时间内完成.
2015-11-07 19:59:07
755
转载 最小表示法和最大表示法详解
以下摘自http://blog.csdn.net/zy691357966/article/details/39854359求字符串的循环最小表示：上面说的两个字符串同构的，并没有直接先求出Min(s)，而是通过指针移动，当某次匹配串长时，那个位置就是Min(s)。而这里的问题就是：不是给定两个串，而是给出一个串，求它的Min(s)，eg：Min(“babba”) = 4。那么由于这里并非要求两个串的
2015-11-07 13:18:15
1505
转载 manacher算法详解
以下摘自http://blog.csdn.net/ggggiqnypgjg/article/details/6645824/首先：大家都知道什么叫回文串吧，这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在O（n）的时间复杂度内既线性时间复杂度的情况下，求出以每个字符为中心的最长回文有多长这个算法有一个很巧妙的地方，它把奇数的回文串和偶数的回文串统一起来考虑了。这一点一直是在做回文
2015-11-07 12:44:09
427
转载 扩展KMP详解
以下摘自http://www.cnblogs.com/yefeng1627/archive/2012/12/24/2830979.html 刘雅琼PPT讲解链接：http://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html扩展KMP： 给出模板串A和子串B，长度分别为lenA和lenB，要求在线性时间内，对于每个A[i]（0 <= i
2015-11-07 11:08:31
820
转载 KMP算法详解
以下转自http://blog.csdn.net/buaa_shang/article/details/9907183 字符串匹配是计算机的基本任务之一。 举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？1. 首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的
2015-11-07 10:05:04
657
原创 HDU - 2888 Check Corners(二维RMQ)
题目大意：给你一个矩阵，Q个询问，询问的是一个矩阵内的最大值，并问这个最大值是否在询问的矩阵的四个角解题思路：二维RMQ裸题#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 310;int n, m;int dp[N][N][9][9];int val[N][
2015-11-06 22:45:42
430
原创 LightOJ - 1081 Square Queries(二维RMQ)
题目大意：给你一个矩阵，然后Q个询问，询问的是一个矩阵内的最大值解题思路：惭愧，这题用了暴力＋一维RMQ#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 510;int n, q, cas = 1;int val[N][N];int dp[N][N][10];
2015-11-06 22:44:05
713
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人