Xiao Luo

@[toc] 简介并查集是用于处理点集之间关系的一种方法，支持合并和查询两种操作，即将两个集合合并和查询两个点是否位于同一集合内，是一种树形数据结构，一般采用数组实现。首先定义一个数组$f$，对于点$i$，$f[i]$存储着i的父节点的下标，通过递归查找找到其根节点。而合并点$i，j$时，首先找到$i，j$的父节点$pi，pj$，然后让$f[pi]=pj$或$f[pj]=pi$即可，也就是让$i，j$所在的集合的根节点同一。查询时只要查询两个点的根节点是否一样即可。 123456789101112131415161718192021int f[100];//存储父节点void ini()//初始化{ for (int i = 1; i <= 100; i++) f[i] = i;//一开始节点i根节点当然是i啦}int find(int i){ if (i == f[i])//如果i的父节点使它本身，说明到头了，i就是根节点 return i; return find(f[i]);//没到头就继续往下找}void merge(int i ...

@[toc] 简介带权并查集是一种带有某种信息的并查集，即每个子节点都储存其自身与跟节点的关系，如路径长度等。定义一个带权并查集数组： 1234struct{ int p;//父节点编号 int data;//与根节点的关系}f[MAX]; 这里关键的问题时带权并查集在合并和路径压缩时怎么做到状态更新呢？ 合并首先合并，除了普通的合并，只要加一条信息更新就行了（更新最终根节点） 12345void merge(int i, int j){ f[i].p = j; update(f[j].data);//j成为了根，更新j } 路径压缩关于路径压缩，先看代码 更新方式112345678int find(int x){ if (f[x].p == x) return x; f[x].p = find(f[x].p); f[x].data = f[f[x].p].data; return f[x].p;} 和普通的路径压缩相比，只是多了一行代码。因为第5行代码执行后，f[x].p已经是根节点，所以这样更新使得子节点的data直接是 ...

@[toc] 简介拓扑排序是将一张有向图的节点进行排序，使得形成的拓扑序满足一个节点的前驱必然在其前面，一个节点的后继必然在其后面。拓扑排序是根据各个节点的入度来实现的（即该节点前驱的个数）。首先先将入度为0的节点扔进队列里（即没有前驱的节点），每次弹出一个节点，即已经将他排好序，把它从图中拿出来。因为该节点已经从图中拿出来了，因此要遍历该节点的所有后继，将它的所有后继入度减一。此时如果他的某一个后继入度减一后变成了0，说明该后继在未排序的节点中它已经没有前驱，那就将它丢进队列中，因为队列是先进先出，所以会依此形成有序循环，直到队列为空。队列为空后，该节点所在的强联通块就已经生成了拓扑序，而未联通的其他分量会不在拓扑序中。而在该联通块中，如果排好的序小于节点数量，说明图中有环。为啥子嘞？因为如果有环的话，环中的节点就会直接的或间接的指向自己，而拓扑排序时的后继检查不检查自己，因此环中节点的入度最后会是1（该唯一前驱为自己）因此拓扑排序同时可以用来判环。 实现12345678910111213141516171819202122232425void topsort(vector<i ...

作者：@houkai转载->http://www.cnblogs.com/houkai/p/3371807.html他讲的太好了。。。。

@[toc] 简介规定点的数量为V，边为E生成树是指在连通图中包含所有节点的一棵树，即该树包含所有节点的同时每个节点的入度出度均为1。而一幅图的生成树有很多种，其中最小生成树指的是带权图的生成树中边权和最小的树。并且若图中的边权都不相同，则最小生成树唯一（每两个节点都只有一条边相连，每次选最小的），反之，就不一定了。最小生成树一般有两个通用的算法，一个是Prim算法，一个是Kruskal算法。 Prim算法Prim算法被形象的描述为一棵小树逐渐长大。首先，先从图中任意选取一个节点，寻找离该节点最近的节点合并形成一棵树，再更新各个相连节点到该树的距离，再找最小，合并直到长成节点树为V的树，即为最小生成树。那在向树添加节点的过程中，怎样更新各节点到树的距离呢？首先，我们可以先定义一个优先队列（一种每次key值最大/最小的元素都在队首的数据结构），每次取结点时，将该节点所有邻接节点都丢入队列（未直接相连的先不管，因为只要是和树未直接相连的节点距离一定小于直接相连的），然后每次从队首中取出一个（距离最子树小的）节点，再更新直到树上有V个节点任务就完成了。 时间复杂度若采用邻接链表存图，优先队列 ...

UVA1218定义：$Son[i]$为第$i$个节点的子节点集$dp[i]$为以$i$为根节点的最少服务器需求量 $dp[i][0]$为将第$i$个节点作为服务器的时的情况，即它的子节点既可以是服务器，又可以是客户端。 $dp[i][1]$为第$i$个节点为客户端且它的父节点为服务器的情况，即它的子节点只能是客户端。（一个客户端只能且必须能和一个服务器直接相连） $dp[i][2]$为第$i$个节点为客户端且它的父节点也为客户端的情况，即i有且只有一个子节点是服务器。 转移方程：$V$为$i$的子节点集合 $dp[i][0]=(\sum\limits_{v\in V}{min(dp[v][0],dp[v][1])})+1$ $dp[i][1]=\sum\limits_{v\in V}{dp[v][2]}$ $dp[i][2]=min(dp[v_k][0]+\sum\limits_{v\in {V-v_k}}{dp[v][2]})=min(dp[v_k][0]+dp[i][1]-dp[v_k][2]$即枚举$i$的每一个子节点作为服务器的情况。 AC代码：12345678910 ...

UVA1631定义：$dp[i][x][y][z]$为达到第$i$个数字之前已经解锁，第$i$个数为$x$，第$i+1$个数为$y$，第$i+2$个数为$z$的状态最少需要转动几下。详见注释AC代码：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<iostream>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<cmath>#include<map>using namespace std;constexpr static int inf = 0x3f3f3f3f;char Start[1002], End[1002];int dp[1001][10][10][10];int Len;int DP(int Cur,int x,int y,int z ...

感谢大佬@角落的秋天的讲解

UVA1673这道题可以用广义后缀自动机，不过陈锋老师给我们讲了一个巧妙地方法，使得这道题可以用普通的后缀自动机做。题目大意：给出$N$个完全由数字组成的字符串。计算将这个$N$的字符串的所有子串转换为整数后先去重再求和的结果，输出其模2012的余数。也就是求其子串的所有本质不同的字符串的和。预处理：首先，我们可以将$N$个字符串拼接起来，拼接的部位可以用一个特殊的分隔符隔开。比如这里我用 ==:==，因为$’:’-‘0’=10$。我们将拼接好的字符串记作$S$，这样问题就转换成求$S$中所有不含分隔符的本质不同的子串的和。对$S$建立后缀自动机。定义：$Cnt[v]$为从$SAM$的初始状态到状态$v$中的所有不含分隔符以及前导0的数量（根据题意，前导0去掉后算一个。比如01和1算作同一个子串）。$Sum[v]$为从初始状态到状态$v$的所有合法路径形成的数字之和。转移方程： Cnt[v]=\sum\limits_{u\in FatherOf(v)}{Cnt[u]}即v由u转移而来。而关于合法转移，只要在转移时不向分隔符的方向走子串就不会出现分隔符；只要不再初始状态往0走，就不会出现 ...

UVA10817定义：$s_0$为没人教的科目的集合，$s_1$为恰好有一人教的科目的集合，$s_2$为至少有两人教的科目的集合。则定义$dp[i][s_1][s_2]$为考虑前i名教师时科目情况为相应科目情况为$s_1,s_2$时的最小花费。$AllSet$为全集。这里的集合采用二进制表示法。$i$的编号从$0\sim M+N-1$，即$0\sim M-1$为在职教师，$M\sim M+N-1$为应聘教师。初始化： dp=-1$$表示未计算过 **转移方程**： 1. 枚举应聘者时 $$dp[i][s_1][s_2]=min(\\ dp[i+1][s_1][s_2]不聘用第i名教师，\\ dp[i+1][s_1'][s_2']+teachers[i].Cost聘用第i名教师\\)其中，$s_1’,s_2’$为聘用此人后的新$s_1,s_2$ 枚举在职教师时,只能聘用dp[i][s_1][s_2]=dp[i+1][s_1'][s_2']+teachers[i].Cost 边界条件：当$i==M+N$时，即$dp[M+N]$要赋值给$dp[M+N-1]$，此时为考虑所有教师后，因此若 ...