Shoutmon-CSDN博客

原创 HDU Air Raid 最小路径覆盖

转载请注明本文地址继续了解了一些概念，比如最小路径覆盖什么的，但总觉得对这些东西现在理解的还不深刻题意：有n个点，m条有向边，无环。求最少数量的路径，使所有点都被这些路径覆盖。思路：1.首先解释一些概念。路径覆盖：在有向无环图中选一些路径，使之覆盖所有的点，并且每个顶点只能有一条边经过。最小路径覆盖：所有上面所述路径中使路径数目最少。2.有向无环

2013-02-22 23:29:27 608

原创 HDU 1150 Machine Schedule 最小点覆盖

转载请注明本文地址学习了二分图的邻接矩阵存储方式，原来二维刚好表示二分图……不是按照所有的点的存法题意：有两个机器A和B，分别有mode_0,mode_1...mode_n-1和mode_0,mode_1...mode_m-1，初始均在mode_0。现在有k个job，每个job可以在A的mode_x或者B的mode_y下完成。每次重新选择模式要重启机器。问最少重启多少次机器

2013-02-22 16:00:09 491

原创 HDU 1179 Ollivanders: Makers of Fine Wands since 382 BC. 最大匹配

转载请注明本文地址题意：n个魔法师，m根魔杖，要配对，一人最多一根魔杖，一根魔杖最多配一个人。求最大匹配数。思路：裸最大匹配，不过题目有点长所以我直接开有道全文翻译了，看懂最后一段就可以了……代码：#include#include#include#include#includeusing namespace std;const int M

2013-02-20 14:48:11 728

原创 HDU 1068 Girls and Boys 最大独立集

转载请注明本文地址刚开始学二分匹配题意：定义“romantically involved”为一男一女搭配。现在有n个人，存在一些已有的搭配。现在希望找出一个集合，在这个集合里的人两两不存在“romantically involved”。思路：1.所求为最大独立集2.二分图中最大独立集=节点数 - 最大匹配3.本题中，由于“romantically i

2013-02-20 14:09:35 610

原创叉姐的教导

“……我的天。”“学一个算法。”“一般都要思考他最general的case。”“我们图论老师说过。”“理解一个定理，最好就是看他每个条件是怎么起作用的。”“对于缺少某个条件的定理，举出相应的反例。”——叉姐

2013-02-19 21:30:23 1247

原创杂记

这样下去速度太慢了，我还是舍弃现在的模式，少写题但阅题无数吧。虽然这样对代码能力提高没有帮助，但毕竟我的分工不是写题，建图+DP成为主攻方向较好。这也是结合了自身情况做的决定……但最简单的写法也还是得会啊……

2013-02-19 19:46:15 499

原创 HDU 3986 Harry Potter and the Final Battle 删除一条边的最长最短路

转载请注明本文地址这题跟这题的题意是一样的，但是也有两点区别：1.1号点到n号点可以不连通 2.有重边。其中第二点可以导致题目变得更麻烦一点。思路：用邻接表写会简单一些，但是我还是用临界矩阵写了。1.整体思路跟上面给的那个链接的做法是一样的，也是枚举最短路上的边（正面见那个链接），然后删除，跑最短路，取最长的那个。2.考虑到每次只删一条边，那么即使有重边，那实际

2013-02-19 18:53:35 628

原创 HDU 1595 find the longest of the shortest 删除一条边的最长最短路

转载请注明本文地址谁能告诉我200ms的是怎么做到的……风神您是怎么做到的orz……题意：给n个点，m条无向边，从1号点到n号点。现在删除其中的一条边，但不知道是哪条。求最坏情况下的最短路长度。思路：先跑一遍最短路，然后枚举最短路经过的边，删之（就是距离设成inf），跑最短路……依次重复，记录最大值即可。证明：假如删除的边不在原来的最短路上，那么删除了之

2013-02-18 23:59:17 1172

原创 HDU 2923 Einbahnstrasse 反向建图

转载请注明本文链接题意：有n个城市（输入字符串名字），m条有向边（是否有向根据输入的箭头决定），已知距离，其中有c个需要到达的城市。要求从一个起始点（给出）分别到达这些城市后返回起始点需要的最短距离。思路：由于输入比较麻烦，所以先写个思路，以后再写代码，思路应该是没有问题的。1.先正向建图，以起始点为源点跑一遍SPFA求出到达所需要到达的城市的最小距离2.再反向建图

2013-02-17 13:49:02 509

原创 HDU 3499 Flight 反向建图

转载请注明本文地址这道题是磊磊师傅教我的第一道反向建图的题目……顺便练习了一下Dijkstra题意：有n个地点，m条有向边，给每条边的花费。允许将任意一条边的花费变为一半（向下取整），求起点a到终点b的最小花费。思路：1.先正向建图，以a为源点跑Dijkstra2.再反向建图，以b为源点跑Dijkstra3.枚举边（作为花费变为一半的边），从a到这条

2013-02-17 02:16:42 1140

原创 HDU 2680 Choose the best route 超级源点or反向建图

转载请注明出处经过然神指点，发现自己对超级源点（广义源点）的做法欠妥，空间太费，这次终于修正了。题意：n个点，m条有向边，其中可以从给定的w个源点中任选一个作为起点，要求到达s号点的最短时间。思路：这样的题目的思路可以有两个：1.一是设立一个超级源点（广义源点），由于题目中点的编号为1-n，因此不妨设0为超级源点，之后将w个可选源点和超级源点的距离设为0

2013-02-17 02:04:40 727

原创 HDU 1546 Idiomatic Phrases Game 简单最短路

转载请注明本文链接这道题对我来说就是被题意坑了……好难懂……跌跌撞撞摸寻着题意过不了样例，在过样例后居然1A了……题意：有一个字典，字典有n个字符串，每个字符串由一些“汉字”组成，所谓的“汉字”是指由连续4个字符组成的“字”，而一个字符串至少有3个“汉字”（例如：12345978ABCD2341，那么1234是第一个“汉字”，5978是第二个“汉字”，……，2341是第三个

2013-02-16 23:03:35 671

原创 HDU 1535 Invitation Cards 正反向建图

转载请注明该文链接题意：有n个车站（n为10^6范围），第一个车站是出发点。现在要从第一个车站安排志愿者去2-n号车站服务，每个车站一人。志愿者早上坐公交车从一号车站出发，晚上从各车站坐公交车回到一号车站。每条线路都有各自的费用。求最小总开销。（假设所有车站一定能到达，每次需要出发或者返回时公交车只载志愿者中的一人）思路：有两种思路：1.以1号车站为源点求SPFA，然后

2013-02-16 20:02:51 802

转载 SPFA的两个优化

SPFA 与堆优化的 Dijkstra 的速度之争不是一天两天了，不过从这次 USACO 月赛题来看，SPFA 用在分层图上会比较慢。标程是堆优化的 Dijkstra，我写了一个非常朴素的 SPFA，只能过 6/11 个点。SPFA 是按照 FIFO 的原则更新距离的，没有考虑到距离标号的作用。实现中 SPFA 有两个非常著名的优化：SLF 和 LLL。　　SLF：Small Label Fi

2013-02-16 20:02:16 1755

原创 HDU 1317 POJ 1932 XYZZY 正负环+最长路

转载请注明本文链接这题if的问题、输入的问题让我作死很多次…感谢磊磊师傅的悉心教导（虽然他很早就睡觉去了……）。写写思路和注意点以及收获吧……题意：有n个房间(n思路：1.首先可以发现，只要知道到第n个房间时最大可以获得多少能量值（当然必须保证中途都大于0），就能知道能否赢。2.考虑到负环情况，跑SPFA的时候最长路负环是不会去循环的，所以负环其实可以不

2013-02-16 02:54:21 1246 1

原创 HDU 1245 Saving James Bond 计算几何建图+最短路

转载请注明该文链接题意：有一个100×100大小的矩形，中心为原点(0,0)，右上角为(50,50)，以原点为圆心，15为直径有一个圆（陆地），旁边是水。水中有许多鳄鱼，给出其坐标。一个人从陆地开始跳，每次最多跳距离d，鳄鱼头可以踩，问跳出矩形外（包含边界）的最短路程是多少，以及相应的步数。思路：1.首先注意浮点型的大于小于这些东西2.建图方法：总共需要n+2个点：

2013-02-15 22:53:52 761

原创 HDU 1217 Arbitrage 乘法最短路

转载请注明该文链接题意：利用汇率赚钱的问题。1单位货币a可以兑换x单位货币b，1单位货币b可以兑换y单位货币c，1单位货币c可以兑换z单位货币a。如果通过这样的一个循环货币a多于1单位，那么就赚钱了（可能要绕的弯很多不只这么两步）。给一些货币的汇率转换，问是否存在这样的环来赚钱。思路：1.首先问是否存在这样的环，很容易想到Bellman-Ford算法判环，但是BF算法只

2013-02-15 22:37:49 559

原创 HDU 1874 畅通工程续最短路算法检验题

转载请注明该文链接题意：给一些结点，一些无向边，给起点a终点b，求最短距离。思路：直接建图跑一遍SPFA（或其他的所有的最短路算法）。可以作为所有最短路算法代码的检验题。代码：dijkstra#include#include#include#includeusing namespace std;const int maxn=210;c

2013-02-15 22:25:08 620

原创 HDU 2112 HDU Today

转载请注明该文链接题意：给一些结点，一些无向边，给起点a终点b（字母输入），求最短距离。思路：直接建图跑一遍SPFA。这里学习了map的一些用法。代码：#include#include#include#include#include#include#include#includeusing namespace std;typedef _

2013-02-15 22:19:10 439

原创 HDU 2066 一个人的旅行超级源点

转载请注明该文链接题意：给一些城市，一些无向边，可以以给定的好几个城市中的任何一个为源点，然后给定了几个城市作为任选其一的终点，求从源点到汇点的最短时间。思路：把所有可设为源点的城市记为超级源点，即任意两个城市之间的距离均为0，然后以任一个起点为源点跑一遍SPFA。枚举所有终点，选最小那个就可以了。修正：经过不断学习，发现我这样做耗费空间比较多（数据较弱所以过了

2013-02-15 22:13:40 525

原创 HDU 3790 最短路径问题

转载请注明该文链接尝试了一下邻接表题意：n个点，m条无向边，每条边都有长度d和花费p，给起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。思路：比普通最短路多了一个花费，但是只在距离相同时要求花费最小，所以只需要在松弛条件上做手脚：当距离相等时如果花费更小那么也进行松弛，即将if(d[v]>d[u]+dis)变为if(

2013-02-15 22:03:02 745 1

原创 HDU 2544 最短路

写一些要点供以后翻阅……转载请注明该文链接题意：n个结点，m条无向边，给起点a终点b，求从a到b最短距离。思路：直接邻接矩阵建图，跑一遍dijkstra或者spfa代码：#include#include#include#include#includeusing namespace std;const int maxn=210;const i

2013-02-15 21:54:34 406

原创 HDU 1548 A strange lift

开始学图论……先从dijkstra开始……写点东西供以后翻阅……转载请注明该文链接题意：有一个电梯，每一层有一个数字k，并有两种选择：选UP会让电梯向上k层，选DOWN会让电梯向下k层。给起点a终点b，问从a到b最少步数。思路：每一层记为一个结点，第i层能到达i-k和i+k层，则在i->i-k与i->i+k各建一条边（前提i-k>=1、i+k代码：#in

2013-02-15 21:43:16 504

Shoutmon的专栏