xia0ji233's blog

最近花点时间看了看网络流，也深度地学习了一下网络流的各个算法，虽然还有一个没学，但是不影响。 概念引入首先我们要先理解一下什么是网络，网络与有向图虽然长得一模一样，但是概念略微不一样，首先网络的边权不代表路径长度，代表流量或者花费。 源点：入读为0的点，只出不进 汇点：出度为0的点，只进不出 在网络中，对于非源点和汇点的所有点，需要满足流入流量之和等于流出流量之和，中间节点不存储任何流量，任何一条边的流量受限于自己的容量限制。 于是有的人就想要求出：这张网络运作起来的时候，总流量最大能有多少。由于容量限制比较复杂，似乎不容易规划一个最佳方案。 such as: 在这里，很容易得出 $s\to t$ 的最大流量就是2，上面一条路，下面一条路，边上的限制都是1，因此总流量为2。这里我们再给出两个概念： 增广 :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差) 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?) 因此我们有了第一个算法：FF。 虽然一般来说基本通不过测试点，但是还是有必要学的 ...

最近复习一下线段树的板子。 线段树就随便写吧，就写给自己看看的，因为即便是我学过板子，也基本会交错很多次。首先一个就是一定在开头加上一句话： 1#define int long long 然后就是push_down的操作，一定是有标记的时候已经加完了，push_down的时候就是把标记分发下去然后给子节点加上值和lazy标记。 在add操作的时候一定要加上先push_down再加。 线段树解决问题的范围要求在线，并且含有区间加法和区间查询的操作，下面是洛谷的板子题并给出标程，也可以当板子用。 板子123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include<bits/stdc++.h>#define int long long#def ...

很开心，图论的知识也是积少成多，回首往昔，我对图论的算法仅限于最短路算法($\text {dijkstra}$)和最小生成树($\text {kruskal&prime}$) 。今天来学学这个 $\text {2-SAT}$ 问题。 2-SAT简介 $\text {SAT}$ 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 $k>2$ 时该问题为 NP 完全的。所以我们只研究 $k=2$ 的情况。 $\text {2-SAT}$，简单的说就是给出 个集合，每个集合有两个元素，已知若干个 ，表示 与 矛盾（其中 与 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。(from OI WIKI) 我想上面说的也比我说的稍微清楚点了，那么他的现实意义是什么呢？比较常见的就是逻辑推导了。 告诉你现在有 A，B，C三个人，且A和B是男生，如果B是男生，那么C是女生。问你这三个人的性别分别是什么，我们很容易可以知道A，B为男， ...

差分约束系统，就是给出一组形如 $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;} 那么我们可以得出结论：$dis[i]$ 一定不会比 $dis[j]+d$ 大，当 $i\to j$ 有一条权值为 ...

前面讲到了spfa，然后有一个判断负环的操作，这个判断负环有更好的思路。 设$cnt[i]$为$s$到$i$的最短路中已经经过的路径条数，如果超过 $n$ 个边，那就说明有 $n-1$ 个点，必产生了负环，如果没有负环绝对是不会找到回路的。 洛谷P3385emm直接给标程吧，就是最朴实无华的 $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_cnt[maxn],in_que[ma ...

勇敢小鸡，不怕困难。时隔多日，又来复习图论算法了，本来想的是搞一下差分约束的，但是发现前置知识是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简介 最长回文子串（英语：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) manacher ...

图论也挺难的，所以我选择复习一下字符串那些算法。 字符串算法第一个很重要的就是匹配了，也就是 $KMP$ 算法，这里的话主要就是计算模式串的 $Next$ 数组。那一位的 $Next$ 数组的值相当于这一位之前的字符串的最大相同前后缀长度。 比如 $baabaa$ 那么它的 $Next$ 数组分别是 $-1\ 0\ 0\ 0\ 1\ 2$ 。 为什么最开始的那个是 $-1$ 呢，因为说了，当前的next所看的字符串是不包括当前字符的，所以第一个的next值所看的字符串其实是一个空串。并且我们可以想象一下，如果第一位它就不匹配，我要跳到哪？答案是模式串指针不跳，匹配串指针要跳。但是一般情况下失配是完全相反的，只有匹配的情况下j会往后跳，所以我们会把第一位失配和匹配的情况归为一类，或者是说特判一下第一位失配的情况，就让它跳到-1，如果跳到-1那么 $i++,j++$ 就好了。 那么接下来我们做一道模板匹配题。 练习为了防止被说水博客，这里就放三题好了。 洛谷P3375标板 $KMP$，只不过就是说，最后要那你输出一下模式串从开头到 $i$ 子串串的最长公共前后缀，这个跟 $Next$ ...

很烦啊，最近复习图论，贼艰难，很多题目基本多多少少都要用树形dp。而我专注于搞图论和数据结构，dp完全就是略知一二，逃避没有用，不会就去学，碰到困难就去面对。 树上dp其实跟普通的dp差不多，甚至会比普通的dp写起来简单，但是前提是要理解。 例题洛谷P1352这个真的是典中典了，我看几乎所有的技术博客都会拿这个当作树形dp的入门题，那我也不例外。 题目分析某大学有 $n$ 个职员，编号为 $1\ldots n$。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 其实我觉得这个跟有依赖的背包题有异曲同工之妙，不通的是，他们不是依赖，而是互斥，选了一个人之后则不能选另一个人。而依赖背包则是选了一个则必须选另外一个，当然另外一个没有这个限制，否则两个物品直接合并一个物品啦。 这里很明显就是 $n$ 个人 $n- ...

洛谷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. 请 ...