ACM

HYSBZ 1015 星球大战(并查集)

HYSBZ 1015 星球大战(并查集)
很好的逆向思维题,我们如果正向去想的话,删除节点肯定比较麻烦复杂,但是如果从后往前,删除节点就变成了增加节点,所以我们从最后删除的一个节点开始往前倒着添加节点,也就是维护一个并查集的事。代码:StatusTimeMemoryLengthLangAccepted2136ms16452kB1210C++#include <iostream> #include <... 继续阅读 »
ACM

CodeForces 690C1-Brain Network (easy)

CodeForces 690C1-Brain Network (easy)
判断是不是一棵树的问题,不能成环。使用Kruskal判断就可以了。题目:http://codeforces.com/problemset/problem/690/C1代码:Memory: 16 KBTime: 15 MSLanguage: GNU G++ 5.1.0Result: Accepted#include<iostream>#includ... 继续阅读 »
ACM

2016HUAS_ACM暑假周测5-A - Simple String Problem

2016HUAS_ACM暑假周测5-A - Simple String Problem
        这傻逼题真的是,一开始看有操作问题,想了想是不是线段树?题目看懂哦,就是个并查集。然后查查查,WA了无数次,说实话我是真的不知道哪里错了。后来干脆直接不优化压缩路径,直接暴力枚举,结果AC,我。。。题目:飞机票直达(A - Simple String Problem)Memory: 156 K... 继续阅读 »
ACM

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

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

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

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