ACM

2016HUAS_ACM暑假集训3-Kruskal、Prim、Dijkstra、Spfa等几种算法的比较

2016HUAS_ACM暑假集训3-Kruskal、Prim、Dijkstra、Spfa等几种算法的比较
一直都是在刷题,从来没总结过算法,这样不好啊,特别是这周,发现这么多算法,好多都有相似之处,所以,来个总结把。下面是总结表:算法时间复杂度关键词特性KruskalO(nlogn)最小生成树算法、 维护森林、 并查集、 路径压缩、 稀疏图Kruskal算法主要是运用了并查集的思想,将集合外的元素加入集合中。这个算法的一个重点在于要先排序,然后按照从小到大的顺序取点不断加入集合。它不像其它几种算法,它... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3 - H - Funny Car Racing

2016HUAS_ACM暑假集训3 - H - Funny Car Racing
H - Funny Car Racing        这个题呢,也是一个计算加权最短路径的题目,只不过它不是单独的加权,还要考虑时间问题,属于动态权值,所以我们在通过某个通道时,判断是直接通过还是等待通过就好了,理论上来说也有好几个算法可以AC,@happy_code就用了spfaAC的。看网上别人的博客都... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3 - B - Frogger

2016HUAS_ACM暑假集训3 - B - Frogger
其实这个题目读懂题目意思就已经成功一半了。下面是从别处找来的翻译。Description一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会,但由于湖水太脏,他不想游泳过去而是跳过去找Fiona。很不幸,Fiona所在的石头距离他有点远,甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3 - POJ 1251 - Jungle Roads

2016HUAS_ACM暑假集训3 - POJ 1251 - Jungle Roads
这个题就是畅通工程的翻版好吗,一样可以用Prim和Kus算法来解。要注意的就是输入输出,cin、cout可能更好用 一以前的代码写的太low,更新了一下代码,prim改为优先队列优化,kruskal删除了一个莫名Wa的父节点交换,还是太年轻啊 题目:飞机票直达(F - Jungle Roads) 下面是代码: Prim算法: #include <iostream> #include &... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3-C - Til the Cows Come Home

2016HUAS_ACM暑假集训3-C - Til the Cows Come Home
        题目意思大概是给出T条边,N个点。求第一个点到第N个点的最短距离。开始是n*n次直接循环,然后挂了,总是出现莫名其妙的数字(memset造成,memset使用要谨慎啊!!!)。后来看博客发现用Dijkstra算法求。从1开始,找出距离当前位置距离最小而且最远的点,然后通过这个点找他能到达的边的距离和当前... 继续阅读 »
ACM

2016HUAS_ACM暑假集训3-G - 还是畅通工程

2016HUAS_ACM暑假集训3-G - 还是畅通工程
G - 还是畅通工程        题目意思是找使公路路径最小。也就是最小生成树。但是这里应该有多种解法,我看了两种解法,一种是Prim最小生成树算法,一种是使用类似并查集思想的Kruskal算法。个人感觉Kruskal算法比prim算法好理解一些,但是Kruskal算法的效率要比Prim低。题目:飞机票直达... 继续阅读 »
ACM

2016HUAS_ACM暑假周测2-C - 小Q系列故事——最佳裁判

2016HUAS_ACM暑假周测2-C - 小Q系列故事——最佳裁判
C - 小Q系列故事——最佳裁判找最佳裁判,这个题我WR7次,TLE一次,尝试了二分法,排序,未果。后来直接查找,找距离最短的那个裁判(这个非常重要)才得以AC,而且时间是0ms。其实排序那里应该是有个距离问题没注意到,就是最短距离的前后编号在原始编号的大小。Description  过去的2012年对小Q来说是很悲催的一年,失恋了12次,每次都要郁闷1个来月。   好在小Q是... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-B - The Suspects

2016HUAS_ACM暑假集训2-B - The Suspects
B - The Suspects这个题是并查集的应用,如何找到可能的患者?我们只需要把和患者(编号0)会牵扯到一起有关联的社团全都加在一个父节点下面就行了,虽然使用了路径压缩算法,但是最后还是可能会存在树高为3的树,所以这里的路径压缩并不彻底,AC的时间比大部分高,还有待优化(其实优化过一次,不过是错的)。#include <iostream> //#includ... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-F - A Simple Problem with Integers

2016HUAS_ACM暑假集训2-F - A Simple Problem with Integers
F - A Simple Problem with Integers        这个题也是二叉搜索树的应用,但是考虑到数据是一个区间更新而不是单点更新,所以每个点都更新的话计算量太大会导致TLE,网上搜索之后看到基本上是使用“lazy”思想。所以更改几行关键代码就能AC了。  &nbs... 继续阅读 »
ACM

2016HUAS_ACM暑假集训2-E-I Hate It

2016HUAS_ACM暑假集训2-E-I Hate It
E - I Hate It这个题嘛,我也只能说坑,感觉二叉搜索树到处都是坑啊。这不过是二叉搜索树的简单应用吗?建树,更新,查找。不可能有错啊。和上一个敌兵布阵一样,我cin、cout也没用了啊,为什么?好吧,继续“I Hate It TLE”搜索。好了,找到了,数组开小了就会TLE,我。。。Description很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是... 继续阅读 »