- 博客(73)
- 收藏
- 关注
RSS订阅原创 最短路算法（Floyd、Dijsktra、Bellman-Ford、SPFA）
最短路算法基本可以分为以下两个步骤：①初始化（任意两边的距离）②松弛操作在图论中，最关键的是如何建图。在最短路算法中，首先要处理数据，在这个时候，要考虑该用那种方式建图。比较常见的建图方式：邻接链表、邻接矩阵、前向星、链式前向星、十字链表。对于这五种建图方式，在这里不做详细讨论，只是大概介绍一下优点和缺点。邻接链表：适合点多的图邻接矩阵：适合边多的图链式前向
2016-02-01 10:39:06
600
原创 hdu 1247 Hat’s Words（Trie）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1247题意：判断某个单词是否由另外两个单词拼接组成。注意：这道题不需要按字典序输出！！！（虽然题目说了）#include#include#include#include#include#include#includeusing namespace std;t
2016-01-06 17:27:43
492
原创 hdu 1394 Minimum Inversion Number（线段树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394题意：给定一个全排列，这道题可以看作求该循环序列的最小逆序数。思路：数据范围只有5000，直接暴力就可以过，187ms。但是可以用线段树来优化，46ms可以过。这道题需要用到一个结论，将一个数移动到序列的最后，逆序数增加(-x+n-1-x)。具体解释一下，去
2015-12-21 00:13:59
578
原创 hdu 1698 Just a Hook(线段树+lazy优化)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698思路：区间更新问题。单点更新卡时，需要用到lazy算法优化一下。下面摘自网上：用到了lazy[] 表示懒惰标志.. 懒惰标记： 就是每次更新不更新到最后..而是更新到包含了区间的最大的节点.. 然后如果下次更新的时候
2015-12-19 23:16:04
432
原创 poj 3463 Sightseeing（最短路和次短路）
题目链接：http://poj.org/problem?id=3463题意：求最短路和次短路的总个数，满足次短路的距离+1=最短路。#include #include #include #include #include #include #include #include #include #include #include #include #i
2015-12-18 10:33:39
441
转载 堪称最好的A*算法
原文地址：http://dev.gameres.com/Program/Abstract/Arithmetic/AmitAStar.mhtAmit's A star Page中译文 译序这篇文章很适合A*算法的初学者，可惜网上没找到翻译版的。本着好东西不敢独享的想法，也为了锻炼一下英文，本人译了这篇文章。由于本人英文水平非常有限，六级考了两次加一块不超过370分
2015-12-17 11:59:32
968
原创 poj 2449 Remmarguts' Date（A*+Dijsktra 求第K短路）
题目链接：http://poj.org/problem?id=2449题意：很直接，求第k短路。思路：没什么思路。参考了网上的资料学习了一波，对链式前向星的了解不够深刻，以前写Dijsktra为了简单粗暴直接用了邻接链表存储图，现在用了链式前向星就不会呃呃呃，毕竟too navie，这也是到现在做的第二个A*的题目，主要目的还是熟悉一下A*算法吧。长路漫漫~#include
2015-12-17 11:42:18
421
转载 深度理解链式前向星
我们首先来看一下什么是前向星.前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.用len[i]来记录所有以i为起点的边在数组中的存储长度.用head[i]记录以i为边集在数组中的第一个存储位置.
2015-12-17 11:39:43
344
原创 poj 3264 Balanced Lineup（线段树）
题目链接：http://poj.org/problem?id=3264思路：线段树，维护最大值最小值之差。一开始蠢得要死，写了两个Query维护最大最小值，后来在网上参考大神的优化了一下。#include #include #include #include #include #include #include #include #include #inc
2015-12-16 00:35:06
298
原创 hdu 1754 I Hate It（线段树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754思路：模板题，练手用吧。#include#include#include#include#include#include#include#include#include#include#include#include#include#include//#
2015-12-16 00:33:32
277
原创 hdu 1166 敌兵布阵（线段树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166思路：线段树入门提，维护单点更新。建树感觉都都差不多，主要在更新和询问两个步骤上变化挺大了，感觉还没有领悟，唉。至于模板，没事的时候手搓几遍，慢慢就熟练了。#include #include #include #include #include #in
2015-12-16 00:23:23
277
原创 hdu 1874 畅通工程续（最短路）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1874思路：注意重边的情况，养成好习惯~#include #include #include #include #include #include #include #include #include #include #include #include #i
2015-12-16 00:19:50
255
原创 hdu 1301 Jungle Roads （最小生成树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1301思路：题目看起来极其吓人= =！其实就是一个裸的最小生成树，把字母对应数字就可以了。#include#include#include#include#include#include#include#include#include#include#include#i
2015-12-16 00:13:03
328
原创 hdu 1102 Constructing Roads +1879 继续畅通工程（MST）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1102思路：过该路已经建好，直接把边权值修改为0即可。这题用Prim和kruskal算法都能过。#include#include#include#include#include#include#include#include#include#include#i
2015-12-16 00:06:06
287
原创 hdu 1281 （二分图匹配）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1281思路：行x看成二分图左边的点，列y看成二分图右边的点，最大匹配就是最多可以放的车的数量。先计算出最大匹配，然后枚举每个点，尝试去掉之后，若匹配数增大，则为“重要点”。#include #include #include #include #include #inc
2015-12-15 23:34:09
344
原创 hdu 1829 A Bug's Life
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1829不想说了，说多了都是泪啊....本来用dsu已经过了，看了discuss可以用二分图过掉，思考一波，敲完代码提交，直接wa到死啊，看了讨论版测试了几组样例都能过，wa了十几发到现在也不知道为什么啊啊啊啊啊...心好累..用0，1表示不同性别的人，若两者性别不同则合并，否则直接b
2015-12-15 18:47:54
240
原创 poj 2513 Colored Sticks(Trie+hash+dsu)
题目链接：http://poj.org/problem?id=2513题意：n个木棍，木棍两个端点分别涂上色，问能否将所有木棍都连接起来，要求是木棍连接的两个端点颜色必须相同。思路：这题用STL会超时，否则可以直接用map+dsu，所以只能用hash，用字典树作出string'到int的映射，然后用并查集判断欧拉回路。无向图判断欧拉回路的条件是：①所有顶点的度数均为
2015-12-15 16:07:29
299
原创 hdu 3038（How Many Answers Are Wrong）+3047（Zjnu Stadium）（种类并查集）
hdu 3038：http://acm.hdu.edu.cn/showproblem.php?pid=3038hdu 3047：http://acm.hdu.edu.cn/showproblem.php?pid=3047如果之前没见过种类并查集的话，估计第一反应都是线段树吧...这两道题都是在压缩路径的时候，利用递归，求得节点到根的距离。用sum[i]表示节点i到根节点
2015-12-14 23:12:34
323
原创 hdu 3635 Dragon Balls（并查集）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3635这题想得好蠢。一开始用cin果断超时了，后来一直wa，纠结一会才发现题目看错了= =！以为是只移动第A颗龙珠，实际上是移动该城市所有龙珠。这题是赤果果的并查集，重点在于路径压缩的妙处。如果每一栋一次就遍历一边将A城市所有龙珠的移动次数+1，肯定会超时。#include
2015-12-14 17:20:33
320
原创 hdu 1532 Drainage Ditches（最大流之Ford-Fulkerson算法）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1532一，概念1）流网络：简单有向图，且有两个特别的顶点（源点s，汇点t）2）流的边标识为f(u,v)/c(u,v)，流量/容量3）流的三个性质：1>容量限制 对于所有边 流量2>反对称性 f(u,v)=-f(v,u)3>流守恒性
2015-12-14 00:06:50
380
原创 hdu 1207 汉诺塔II
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1207多柱汉诺塔最优算法设计探究：http://www.cnblogs.com/fanzhidongyzby/archive/2012/07/28/2613173.html这题是一个四柱汉诺塔问题，基于J. S. Frame算法，具体参考上述链接。Frame算法的递归
2015-12-13 16:32:33
345
原创 hdu 1195 Open the Lock（BFS && DBFS）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1195推荐一个个人感觉讲解得比较好的DBFS的博客http://blog.sina.com.cn/s/blog_8627bf080100ticx.html 所谓双向广搜，就是初始结点向目标结点和目标结点向初始结点同时扩展，直至在两个扩展方向上出现同一个结点，
2015-12-13 15:49:51
307
原创 hdu 5265 pog loves szh II
pog loves szh IITime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2279 Accepted Submission(s): 656Problem DescriptionPog an
2015-12-11 21:08:48
376
原创 hdu 1716 排列2（水题）
排列2Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6084 Accepted Submission(s): 2332Problem DescriptionRay又对数字的列产生了兴趣：现
2015-12-10 20:13:52
352
原创 hdu 1878 欧拉回路（水题，判断欧拉回路）
判断一个图中是否存在欧拉回路（每条边恰好只走一次，并能回到出发点的路径），在以下三种情况中有三种不同的算法：一、无向图每个顶点的度数都是偶数，则存在欧拉回路。二、有向图（所有边都是单向的）每个节顶点的入度都等于出度，则存在欧拉回路。以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。三、混合图（有的边是单向的，有的边是无向的。常被用于比喻城市里的交通网
2015-12-10 10:41:11
339
原创 hdu 1244 Max Sum Plus Plus Plus（DP）
Max Sum Plus Plus PlusTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1519 Accepted Submission(s): 754Problem Description
2015-12-09 23:47:28
301
原创 hdu 1246 自共轭Ferrers图（DP）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1246#include #include #include #include #include #include #include #include #include #include #include #include #include #include #in
2015-12-09 21:36:18
631
原创 POJ 3268 Silver Cow Party（Dijsktra+优先队列）
奶牛派对：有分别来自 N 个农场的 N 头牛去农场 X 嗨皮，农场间由 M 条有向路径连接。每头牛来回都挑最短的路走，求它们走的路的最大长度？#include #include #include #include #include #include #include #include #include #include #include #include #in
2015-12-09 16:15:13
267
原创 hdu 1520Anniversary party(树形dp)
Anniversary partyTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 7539 Accepted Submission(s): 3310Problem DescriptionTher
2015-12-07 15:58:51
285
转载 string和stringstream用法总结
一、stringstring 是 C++ 提供的字串型態，和 C 的字串相比，除了有不限长度的优点外，还有其他许多方便的功能。要使用 string， 必須先加入这一行：#include 接下來要宣告一个字串变量，可以写成：string s;我们也可以在宣告的同时让它设成某个字串：string s="TCGS";而要取得其中某一個字元，和传统C 的字串
2015-12-04 14:26:33
313
原创 hdu 1198Farm Irrigation（并查集）
Farm IrrigationTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 7663 Accepted Submission(s): 3289Problem DescriptionBenny has
2015-12-04 12:42:29
295
原创 hdu 巴仕博弈(1846+2149+2897)
hdu1846:http://acm.hdu.edu.cn/showproblem.php?pid=1846#include #include #include #include #include #include #include #include #include #include #include #include #include #include #i
2015-12-02 22:26:36
383
转载 博弈论基础知识: 巴什博奕+威佐夫博奕+尼姆博弈(及Staircase
(一)巴什博奕(Bash Game):只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个.最后取光者得胜.若(m+1) | n，则先手必败，否则先手必胜。显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜.因此我们发现了如何取胜的法则：如果n=(m+1)r+s,(r为任意自然数,s≤m),
2015-12-02 21:42:05
397
原创 hdu 2189（简单完全背包）
题意：将n分成若干个素数之和，问有多少中方式。思路：素数打表，然后完全背包。（也可以用母函数）#include #include #include #include #include #include #include #include #include #include #include #include #include #include #
2015-12-02 21:24:35
519
原创 hdu 2141 Can you find it?（暴力+二分）
Can you find it?Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/10000 K (Java/Others)Total Submission(s): 19048 Accepted Submission(s): 4801Problem DescriptionGiv
2015-12-01 21:25:04
340
原创 hdu 1285 确定比赛名次（拓扑排序）
确定比赛名次Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18377 Accepted Submission(s): 7355Problem Description有N个比赛队（1
2015-11-30 16:18:42
291
原创 hdu 2444 The Accomodation of Students（判断二分图+匈牙利算法）
The Accomodation of StudentsTime Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4085 Accepted Submission(s): 1873Problem Descri
2015-11-28 13:21:56
339
原创 POJ 3041 Asteroids（二分图匹配+匈牙利算法）
AsteroidsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 18296 Accepted: 9973DescriptionBessie wants to navigate her spaceship through a dangerous asteroid field in the shape of
2015-11-28 11:25:59
440
原创 hdu 3460 Ancient Printer（贪心 or Trie树）
Ancient PrinterTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)Total Submission(s): 1507 Accepted Submission(s): 744Problem DescriptionThe co
2015-11-28 11:22:27
333
原创 hdu 2063 过山车（纯裸hungary算法）
过山车Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 15344 Accepted Submission(s): 6722Problem DescriptionRPG girls今天和大家一起去
2015-11-26 18:26:39
356
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人