ZOJ_3261_逆并查集 ZOJ 3261 逆并查集 思路简单代码繁琐一直wa调了一天，真的菜 因为并查集没有摧毁边的操作,那我们不妨先合并所有边中 不会被摧毁的边,那么就需要我们先保存所有的边,(这里太繁琐容易出错) 开一个数组记录每个点的值,因为要找值最大 或者 值相同但点最小的点,在合并的时候根据这个来合并,值小的指向值大的,(值相同时,大点指向小点) 这里用了一个技巧就是 map<pair<int 2019-05-19 算法
2013_格子刷油漆_(dp) 开2个数组 a[]表示在2*N的格子,从四个顶点中任意一个格子出发遍历全部格子的种类数,a[1] = 1 a[2] = 6(画出所有情况) b[]表示在2*N的格子,从任意一个格子出发,遍历所有格子且终点在出发点这一列,以为要回来,所有每一步只能一直往左或者右走(这样该列另一个格子就会留个回来时刷),所以每一步2中选择,b[i] = 2 * b[i-1] 出发点在四个顶点处,考虑a 2019-05-19 算法
HDU_1272_(并查集) HDU 1272 无向图用并查集判断是否成环. 坑点：仅仅考虑了根节点相同(有回路)的情况,而忽略了有多个连通分量,也是不满足 任意两个房间有且仅有一条路径相同123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream&g 2019-05-17 算法
POJ_1984_(带权并查集) POJ 1984 自己审题问题极其严重 1.忽略了该题询问i行可能询问多次， 2.忽略了给出询问行不是按顺序的排序的，我以为是按顺序， 没有想出怎么用带权并查集做 根据给出的东南西北来维护dx横坐标到根节点距离 dy纵坐标到根节点距离, 路径压缩的时候dx dy一起压缩就行,主要是合并的时候根据题目给出的东南西北来确定dx dy 合并根节点 还是rala[ra] = rala[b] 2019-05-17 算法
POJ_1733_(并查集+离散化) POJ 1733 带权并查集 权值既可以通过异或来表示奇偶的数量，也可以直接存奇偶数量1 2,路径压缩的时候累加起来就行了 此题点的范围太大,需要离散化,注意输入的次数最多为5000,则最多有1e4个点， 带权并查集+离散化1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 2019-05-17 算法
HDU_3038_(并查集合并 线性加) HDU 3038 加权并查集 题目描述有问题，有多组数据 子序列是连续的，路径压缩是权值相加就行， 根节点相同说明已经存在合理字段和，判断到根节点的距离是否满足 已经存在的和 不同则合并 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream 2019-05-17 算法
POJ_2236_(并查集小变形) POJ 2236 2层循环找出每个点 周围与其距离<=d的点，vector<int> p[maxn]记录, O的意思是修复O附近的点,但是必须是已经出现过的需要被修复的点,(从样例我们可以看出来),用vis[]标记一下需要修复的点, 其他的就是并查集了12345678910111213141516171819202122232425262728293031323334353 2019-05-16 算法
POJ_1702_(带权并查集) POJ 1703 此题2种情况，一种情况是确定种类不同,另一种就是询问同类的关系 注意scanf()读取 还是开一个数组rala[]记录该点与父节点的关系，1表示不同类,0表示同类,在路径压缩到根节点的同时，每一步都进行 该点rala[i]与父节点rala[pre[i]]关系异或rala[i]^rala[pre[i]],这样能使关系保持相同，并且每点只想根节点, 询问就是 判断根节点是否相 2019-05-16 算法
POJ_2524(并查集模板) POJ 2524并查集模板题 123456789101112131415161718192021222324252627282930313233343536#include <iostream>using namespace std;const int maxn = 5e4+10;int pre[maxn];int n,m;void init(int k) { for 2019-05-16 算法
POJ_2492_(带权并查集) POj 2492 关系异或加权并查集 无法确定bug具体是男还是女,只能知道他们是同性还是异性 都合并到一个数中，通过边的权值来记录是同性还是异性 开一个数组rala[]记录点i与点i的父亲节点的关系,1代表性别不同,0代表性别相同 给出的2点肯定是异性，先判2点断根节点是否一样，相同就通过2点分别推根节点的性别是否一样，一样就正好已经在树中，不一样则不满足教授推论 根节点不一样就合并根节 2019-05-16 算法