前言 EK算法是求网络最大流的最基础的算法,也是比较好理解的一种算法,利用它可以解决绝大多数最大流问题. 但是受到时间复杂度的限制,这种算法常常有TLE的风险 思想 还记得我们在介绍最大流的时候提到的求解思路么? 对一张网络流图,每次找出它的最小的残量(能增广的量),对其进行增广. 没错,EK算法就是利用这种思想来解决问题的 实现 EK算法在实现时,需要对整张图遍历一边. 那我们如何进行遍历呢?BFS还是DFS? 因为DFS的搜索顺序的原因,所以某些毒瘤出题人会构造数据卡你,具体怎么卡应该比较简

题目: 不难看出题意主要是给出ml+md个格式为xi-xj<=ak的不等式,xi-xj为i,j俩头牛的距离,要我们求x1-xn的最大值. 经过上下加减我们可以将这几个不等式化成x1-xn<=a1+a2+a3+a4+....+ak,在这加减的过程中我们不难看到dijstra的身影,这加加减减的过程不正是松弛操作吗! 这时我们就得到了正解——差分约束算法,此算法主要用于处理差分约束系统:如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则

洛谷 P3805 [模板]manacher算法 洛谷传送门 题目描述 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 字符串长度为n 输入格式 一行小写英文字符a,b,c...y,z组成的字符串S 输出格式 一个整数表示答案 输入输出样例 输入 #1复制 输出 #1复制 说明/提示 字符串长度len <= 11000000 题解: 都说了是\(Manacher\)算法的模板了... 关于马拉车算法,如有不懂请参考本蒟蒻的这篇博客: 详解Manacher算法

洛谷题目传送门 萝卜大毒瘤 题意可以简化成这样:给一个DAG,求每个点能够从多少个入度为\(0\)的点到达(记为\(k\)). 一个随机做法:给每个入度为\(0\)的点随机一个权值,在DAG上求出每个点能够返回到的入度为\(0\)的点的最小权值,那么这个权值的期望是\(\frac{\text{随机值域}}{k+1}\).多选几套随机权值(蒟蒻选了一百次),跑出来的平均值即可输出. 实在是太玄学了. #include<bits/stdc++.h> #define LL unsigned long

洛谷题目传送门 %%%TPLY巨佬和ysner巨佬%%% 他们的题解 思路分析 具体思路都在各位巨佬的题解中.这题做法挺多的,我就不对每个都详细讲了,泛泛而谈吧. 大多数算法都要用kruskal把最小生成树弄出来,因为要求次小生成树.至于为什么次小一定只在最小的基础上改变了一条边,我也不会严谨的证明......打表找规律大法好 剩下的可以有一堆数据结构来维护最大值和次大值(原理两位巨佬都讲清楚了,这里只分析一下算法的优劣) kruscal+倍增+LCA 山楠巨佬的做法,我也写了这一种.复杂度\(

洛谷题目传送门 \(O(n)\)的正解算法对我这个小蒟蒻真的还有点思维难度.洛谷题解里都讲得很好. 考试的时候一看到300000就直接去想各种带log的做法了,反正不怕T...... 我永远只会有最直观的思路(最差的程序效率) 题目相当于每次让我们找区间\([1,las-1]\)中上数第一个比当前盘子半径小的位置(las为上一次盘子掉到的位置)于是用线段树无脑搞一下,维护区间最小值,每次找这个位置,能往左跳就往左,不能的话再往右,当然如果超过了las-1就不用找了,直接放在las上面(相当于la

洛谷题目传送门 了解网络流和dinic算法请点这里(感谢SYCstudio) 题目 题目背景 这本是一个非常简单的问题,然而奶牛们由于下雨已经非常混乱,无法完成这一计算,于是这个任务就交给了你.(奶牛混乱的原因看题目描述) 题目描述 在一个农场里有n块田地.某天下午,有一群牛在田地里吃草,他们分散在农场的诸多田地上,农场由m条无向的路连接,每条路有不同的长度. 突然,天降大雨,奶牛们非常混乱,想要快点去躲雨.已知每个田地都建立有一个牛棚,但是每个牛棚只能容纳一定数量的牛躲雨,如果超过这个数量,那

洛谷题目传送门 设抛物线方程为\(y=ax^2+bx(a<0,b>0)\),我们想要求出一组\(a,b\)使得它尽可能满足更多的要求.这个显然可以二分答案. 如何check当前的\(mid\)是否合法呢?每一个限制条件形如\(y_{i_1}\le ax_i^2+bx_i\le y_{i_2}\),也就是\(\frac{y_{i_1}}{x_i}\le x_ia+b\le \frac{y_{i_2}}{x_i}\).把\(a,b\)看成自变量,实际上每个不等式就是一个半平面,我们需要求出半平面交

洛谷题目传送门 \(O(n)\)算法来啦! 复杂度优化的思路是建立在倍增思路的基础上的,看看楼上几位巨佬的描述吧. 首先数组倍长是一样的.倍增法对于快速找到\(j\)满足\(l_j+m\le r_i\)进行了优化.然后菊开队长说可以建个树优化,可是他没讲清楚就把这个神仙东西扔给了我这个蒟蒻...一个晚上终于把这个模性建出来了. 在倍长的序列上,我们对于每一个\(i\)找到最小的\(j\)满足\(r_j\ge l_i\)并连一条\(i\)到\(j\)的边,于是就成了一个森林.贪心地想,我们要求的东

洛谷题目传送门 疯狂%%%几个月前就秒了此题的Tyher巨佬 借着这题总结一下决策单调性优化DP吧.蒟蒻觉得用数形结合的思想能够轻松地理解它. 首先,题目要我们求所有的\(p_i\),那么把式子变一下 \[p_i\ge a_j-a_i+\sqrt{|i-j|}\] \[p_i=\max\limits_{j=1}^n\{a_j+\sqrt{|i-j|}\}-a_i\] 绝对值看着很不爽,我们把它拆开 \[p_i=\max(\max_{j=1}^i\{a_j+\sqrt{i-j}\},\max_{j

洛谷题目传送门 DP题怕是都要大大的脑洞...... 首先,时间那么大没用,直接离散化. 第一问还好.根据题意容易发现,当一堆活动的时间有大量重叠的时候,更好的办法是把它们全部安排到一边去.那么我们转移的时候也肯定是要一块一块地转移啦. 设\(tot_{l,r}\)为完全被包含在\(l-r\)时间内活动总数,直接\(O(n^3)\)暴力求就好了. 设\(pre_{i,j}\)为时间\(1-i\)内一边选\(j\)个时,另一边能选的最大值.枚举一块转移的话,我们的方程应该写成这样: \[pre_

洛谷题目传送门 HNOI爆零前回刷模板题 非常不正经的题目,目前并没有合适的优秀算法,就算是大家公认的dfs(还是不要强行叫dfs-spfa吧,概念应该不一样,这就是暴力dfs松弛答案) 但是对于随机数据来说,dfs有着优秀的效率,可以快速发现负环并退出 从每个点开始暴力dfs,记一个bool数组ins表示每个点是否在搜索栈中.如果发现可以松弛并且踏进了已经在栈中的点就说明找到了负环. 注意几点: YE5和N0 2333 dis初始化为0,因为只要判负环,正权一开始并不用松弛 因为并没有说图连通

洛谷题目传送门 说不定比官方sol里的某理论最优算法还优秀一点? 所以\(n,m\)说不定可以出到\(1000\)? 无所谓啦,反正是个得分题.Orz良心出题人,暴力有70分2333 思路分析 正解的思路很巧妙,其实我并不觉得这是个正儿八经的网络流或者二分图匹配的题目,主要还是个思维+建图模型+乱搞...... \(C=1\)时我们就可以对于每个人直接匹配而不会影响到后面的选择了.但是\(C>1\)的话,可能某一个人可以选多个导师,当他随便选了其中一个以后,可能影响到后面某个人使其选不到本来的最

洛谷题目传送门 思路分析 最简单粗暴的想法,肯定是大力LCT,每个树都来一遍link之类的操作啦(T飞就不说了) 考虑如何优化算法.如果没有1操作,肯定每个树都长一样.有了1操作,就来仔细分析一下对不同树的影响. 假设有一个1操作形如\(l\ r\ x\),那么从微观来看差异,我们只关注第l-1棵树和第l棵树.再假设以后都没有了0操作,那么我们可以认为,第l棵树是第l-1棵树把这个1操作以后嫁接在原来生长节点上的所有节点(以及所有子树)全部转而嫁接到x上.再看第r棵树和第r+1棵树,是不是可以认

洛谷题目传送门 最无脑LCT题解,Dalao们的各种算法都比这个好多啦... 唯一的好处就是只管码代码就好了 开战cut,停战link,询问findroot判连通性 太无脑,应该不用打注释了.常数大就不用说了(逃 #include<cstdio> #include<cstdlib> #define R register int #define I inline void #define lc c[x][0] #define rc c[x][1] #define G ch=getch

Update:原来的洛谷U21715已成坑qwq 已经被某位管理员巨佬放进公共题库啦!又可以多一个AC记录啦! 洛谷题目传送门 其实也可以到这里交啦 思路分析 动态维护树的重心 题目中说到国家的首都会选在某个使得其他城市到它距离之和最小的城市,那不就是树的重心了嘛.树的重心性质真的很好,看看wuhulala巨佬的这篇博客. 网上大多数解法都是启发式合并.利用了以重心为根的子树大小不超过原树的一半,每次合并两颗树的时候,小的往大的上面合并,而且是一个点一个点地link上去,每次link完检查一下这

洛谷题目传送门 %%%TPLY巨佬和ysner巨佬%%% 他们的题解 思路分析 具体思路都在各位巨佬的题解中.这题做法挺多的,我就不对每个都详细讲了,泛泛而谈吧. 大多数算法都要用kruskal把最小生成树弄出来,因为要求次小生成树.至于为什么次小一定只在最小的基础上改变了一条边,我也不会严谨的证明......打表找规律大法好 剩下的可以有一堆数据结构来维护最大值和次大值(原理两位巨佬都讲清楚了,这里只分析一下算法的优劣) kruscal+倍增+LCA 山楠巨佬的做法,我也写了这一种.复杂度\(

洛谷题目链接:[USACO5.5]隐藏口令Hidden Password 题目描述 有时候程序员有很奇怪的方法来隐藏他们的口令.Binny会选择一个字符串S(由N个小写字母组成,5<=N<=5,000,000),然后他把S顺时针绕成一个圈,每次取一个做开头字母并顺时针依次取字母而组成一个字符串.这样将得到一些字符串,他把它们排序后取出第一个字符串.把这个字符串的第一个字母在原字符串中的位置-1做为口令. 如字符串alabala,按操作的到7个字符串,排序后得: aalabal abalaal

洛谷题目链接:[USACO5.4]周游加拿大Canada Tour 题目描述 你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票.旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行,直到你到达最东边的城市,再由东向西返回,直到你回到开始的城市.除了旅行开始的城市之外,每个城市只能访问一次,因为开始的城市必定要被访问两次(在旅行的开始和结束). 当然不允许使用其他公司的航线或者用其他的交通工具. 给出这个航空公司开放的城市的列表,和两两城市之间的直达航线列表.找出能够访问尽可能多

洛谷题目链接:[USACO5.3]窗体面积Window Area 题目描述 你刚刚接手一项窗体界面工程.窗体界面还算简单,而且幸运的是,你不必显示实际的窗体.有 5 种基本操作: 创建一个新窗体 将窗体置顶 将窗体置底 删除一个窗体 输出窗体可见部分的百分比(就是,不被其它窗体覆盖的部分). 在输入文件中,操作以如下的格式出现. 创建一个新窗体:w(I,x,y,X,Y) 将窗体置顶: t(I) 将窗体置底: b(I) 删除一个窗体:d(I) 输出窗体可见部分的百分比:s(I) I 是每个窗体唯一

洛谷题目链接:[SDOI2011]消防 题目描述 某个国家有n个城市,这n个城市中任意两个都连通且有唯一一条路径,每条连通两个城市的道路的长度为zi(zi<=1000). 这个国家的人对火焰有超越宇宙的热情,所以这个国家最兴旺的行业是消防业.由于政府对国民的热情忍无可忍(大量的消防经费开销)可是却又无可奈何(总统竞选的国民支持率),所以只能想尽方法提高消防能力. 现在这个国家的经费足以在一条边长度和不超过s的路径(两端都是城市)上建立消防枢纽,为了尽量提高枢纽的利用率,要求其他所有城市到这条路径