差分约束的学习笔记
差分约束系统,就是给出一组形如 \(x_i-x_j\le
d\)
的不等式,求出这组不等式的一组解。这类问题通常转化为图论中的最短路来解。
原理
那我们转换一下,假设 \(x_i\) 为点
\(i\) 的单源最短路长度,\(x_j\) 为点 \(j\)
的单源最短路长度。那么以上不等式就可以转换成 \(dis[i]-dis[j]\le d\to dis[i]\le
dis[j]+d\)。
那么这个就转变成了 \(j\to i\)
一条权值为 \(d\)
的边的最短路搜索了。因为如果一条边 \(i\to
j\) 权值为 \(d\) ,那么必然有
\(dis[i]\le dis[j]+d\)
,如果不满足这个条件。我们用反证法证明一下这个结论,设一条边 \(i\to j\) 权值为 \(d\),且满足 \(dis[i] >
dis[j]+d\),那么在一次单源最短路算法时,必然会导致 \(i\) 点被松弛。即发生
123if(dis[i]>dis[j]+d){ dis[i]=dis[j]+d;}
那么我们可以得出结论 ...
负环判断
前面讲到了spfa,然后有一个判断负环的操作,这个判断负环有更好的思路。
设\(cnt[i]\)为\(s\)到\(i\)的最短路中已经经过的路径条数,如果超过
\(n\) 个边,那就说明有 \(n-1\)
个点,必产生了负环,如果没有负环绝对是不会找到回路的。
洛谷P3385
emm直接给标程吧,就是最朴实无华的 \(spfa\) 负环判断。
标程
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<bits/stdc++.h>#define maxn 2005using namespace std;struct eee{ int next; int to; int w;}edge[maxn<<2];int root[maxn],dis[maxn],e ...
spfa算法的学习
勇敢小鸡,不怕困难。时隔多日,又来复习图论算法了,本来想的是搞一下差分约束的,但是发现前置知识是spfa算法,所以就先来学习一下这个。
spfa算法介绍
SPFA算法是求解单源最短路径问题的一种算法,由理查德·贝尔曼(Richard
Bellman) 和 莱斯特·福特 创立的。有时候这种算法也被称为
Moore-Bellman-Ford 算法,因为 Edward F. Moore
也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作,得到所有可能的最短路径。其优于dijkstra算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达
O(VE)。但算法可以进行若干种优化,提高了效率。
算法的思路:
我们用数组dis记录每个结点的最短路径估计值,用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行 ...
manacher的学习
今天学习一下新的字符串算法——manacher算法。
manacher简介
最长回文子串(英语:Longest palindromic
substring)是计算机科学中的问题,在一个字符串中查找一个最长的连续的回文的子串,例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的,比如在“abracadabra”中,没有超过3个字符的回文子串,但是有两个回文字符串长度都是3:“ada”和“aca”。在一些应用中,我们求出全部的极大回文子串(不被其他回文串包含的回文子串)。
Manacher于1975年发现了一种线性时间算法[1],可以在列出给定字符串中从任意位置开始的所有回文子串。并且,Apostolico,
Breslauer & Galil [2]发现,同样的算法也可以在任意位置查找全部极大回文子串,并且时间复杂度是线性的。因此,他们提供了一种时间复杂度为线性的最长回文子串解法。另外,Jeuring
(1994)[3],
Gusfield (1997)[4]发现了基于后缀树的算法。也存在已知的高效并行算法。(from
wiki) ...
KMP算法的学习
图论也挺难的,所以我选择复习一下字符串那些算法。
字符串算法第一个很重要的就是匹配了,也就是 \(KMP\) 算法,这里的话主要就是计算模式串的
\(Next\) 数组。那一位的 \(Next\)
数组的值相当于这一位之前的字符串的最大相同前后缀长度。
比如 \(baabaa\) 那么它的 \(Next\) 数组分别是 \(-1\ 0\ 0\ 0\ 1\ 2\) 。
为什么最开始的那个是 \(-1\)
呢,因为说了,当前的next所看的字符串是不包括当前字符的,所以第一个的next值所看的字符串其实是一个空串。并且我们可以想象一下,如果第一位它就不匹配,我要跳到哪?答案是模式串指针不跳,匹配串指针要跳。但是一般情况下失配是完全相反的,只有匹配的情况下j会往后跳,所以我们会把第一位失配和匹配的情况归为一类,或者是说特判一下第一位失配的情况,就让它跳到-1,如果跳到-1那么
\(i++,j++\) 就好了。
那么接下来我们做一道模板匹配题。
练习
为了防止被说水博客,这里就放三题好了。
洛谷P3375
标板 \(KMP\),只不过就是说,最后要那你输出一下模式串 ...
树形dp的学习
很烦啊,最近复习图论,贼艰难,很多题目基本多多少少都要用树形dp。而我专注于搞图论和数据结构,dp完全就是略知一二,逃避没有用,不会就去学,碰到困难就去面对。
树上dp其实跟普通的dp差不多,甚至会比普通的dp写起来简单,但是前提是要理解。
例题
洛谷P1352这个真的是典中典了,我看几乎所有的技术博客都会拿这个当作树形dp的入门题,那我也不例外。
题目分析
某大学有 \(n\) 个职员,编号为 \(1\ldots n\)。
他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。
现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\),但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。
所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
其实我觉得这个跟有依赖的背包题有异曲同工之妙,不通的是,他们不是依赖,而是互斥,选了一个人之后则不能选另一个人。而依赖背包则是选了一个则必须选另外一个,当然另外一个没有这个限制,否则两个物品直接合并一个物品啦。
...
洛谷P1948题解
洛谷P1948题解。
题目描述
多年以后,笨笨长大了,成为了电话线布置师。由于地震使得某市的电话线全部损坏,笨笨是负责接到震中市的负责人。该市周围分布着\(N(1<=N<=1000)\)根据\(1……n\)顺序编号的废弃的电话线杆,任意两根线杆之间没有电话线连接,一共有\(p(1<=p<=10000)\)对电话杆可以拉电话线。其他的由于地震使得无法连接。
第i对电线杆的两个端点分别是\(a_i,b_i\),它们的距离为\(l_i(1<=l_i<=1000000)\)。数据中每对\((a_i,b_i)\)只出现一次。编号为1的电话杆已经接入了全国的电话网络,整个市的电话线全都连到了编号N的电话线杆上。也就是说,笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径,其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆,对于此外的那些电话线,需要为它们付费,总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对,那么支出为0.
请你计算一下,将电话线引导 ...
ZJCPC-D. Shortest Path Query
今天来复盘一下上次省赛考到的题目,异常地折磨人。
先说一下这题比赛的情况吧,基本上呢,银奖中等偏上的队伍都是做出来了的。
那我们就看看这题吧。
题目简介
什么思路在题目名字这里就一目了然了,那自然是最短路径。
而当我一眼扫过去看到这个数据量的时候瞬间惊呆。\(1≤n≤100000,1≤m≤200000\),不仅如此,还有
\(q\) 次询问最短路径,\(q≤200000\)
当时一看,这玩你妈。给一个点都勉强能过了,这有这么多点,如果按照常规思路,一次单源最短路径复杂度
\(nlog_2n\) 然后 \(q\) 次询问,总复杂度就是 \(qnlog_2n\)
全部以最大值带进去妥妥的超时。所以当时比赛的时候看到这个题目是直接放弃了的,而且英文不好的我留下了悔恨的眼泪。
题目分析
但是它还有一个条件,那就是,直接相连的两个点当中,其中一个点的编号一定是另一个点的二进制前缀,这就说明了一点,\(2\) 它一定不会跟 \(3,6,12……\) 等点连接起来的,因为它们的前缀是
\(11_{2}\),而 \(2_{10}\) 是 \(10_{2}\)
开头的, ...
LCA算法
最近来复习一遍图论的板子——LCA。
概念
最近公共祖先(英语:lowest common
ancestor)是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里,我们定义一个节点也是其自己的后代,因此如果v是w的后代,那么w就是v和w的最近公共祖先。(fron
wiki)
算法设计
我们先来看看应该怎么解决此类问题。
一般思路
在一个树上,我们定义离根节点最远的与a,b相同的祖先为最近公共祖先(LCA)。我们需要怎么做呢,首先肯定是
dfs 跑一遍,把所有的点的层次遍历出来,时间复杂度为 \(O(N)\)。一般情况下 \(LCA\) 问题会有多次询问,询问次数一般为
\(q<10^5\)
,那么就意味着我们不能在线性时间内去计算 \(LCA\),如果采取最朴素的方法:选定2个点,若深度不一样则先转为深度一样,深度较深的点不停求它的父亲节点直到深度一样,然后用如下代码去求解。
1234567int LCA(int a,int b){ while(a!=b){ a=pre[a]; b ...
洛谷P6037题解
洛谷P6037题解
浅谈基环树(环套树)
在题目开始之前,就唠一唠这个叫基环树的结构。准确来说,基环树它已经不是树了,我们知道,树一定是由
\(n\) 点和 \(n-1\) 条边组成的。而基环树是由 \(n\) 点与 \(n\)
边组成。但是因为它跟树还是很像,并且在保证连通的情况下有且仅有一个简单环,因此得名。如果不连通,那么它会成为基环树森林。
比如上图就是一个基环树。我们可以很清楚的看出来,点 \(2,1,3,7\)
形成了环,断开任意一条属于环中的边都会使这个棵基环树成为树。一般情况下都是将环和环连接的子树进行分开讨论。如何求环呢?我们只需要
dfs
一遍就行了,如果遇到被访问过的点,那就依次返回路径上的所有点,直到我遇到的那个点为止。
举个例子,在上图中,我从 6 开始 dfs,假设它经历了 \(6 \to 2 \to 1 \to 3 \to 7\)
的顺序。那么接下来在搜索 7 的时候就会发现与它相连的点 2
已经被访问过,那么我返回值给个 2,依次回溯,回溯过程中将点入栈或者入一个
\(vector\) 都可以。直到回溯到 2
这个点为止 ...