有源汇上下界最大流 例题 loj116 给出一个有源汇点的有向图。每条边有最大流量和最小流量。现在需要求出从源点到汇点的最大流可以是多少。 前置知识 上下界可行流 思路 先回顾有源汇上下界可行流干了些什么。 其实可行流就是找到了一种满足流量下界的方案。 在满足了流量下界之后，可以发现还有一些残余的自由流量(可选可不选) 于是我们在之前的残余网络上再跑一边\(dinic\)。这次不算超级源汇点，也不算从\(T\)到\(S\)添的那条边。 这样将在可行流种算出来的流量加上后来跑出来的流量就是答案了。 代码 /* * @Author: wx...

无源汇上下界可行流 题目 给出一个有向图。每条边有流量上界和下界，问是否存在一中流量分配方案，使得每个点流量守恒(即流入量=流出量) 思路 解决这种问题的主体思路就是在初始流的基础上不断添加流量，使得满足流量守恒。 初始流很显然应该是每条边流量的下界。 但是这样并不满足流量守恒。然后考虑添加流量。 对于一个点，我们设初始流中他的流入量为\(rd\)，流出量为\(cd\)。设\(d=rd-cd\)。 然后对\(d\)进行分类讨论。 如果\(d < 0\)，则表示流入量要比流出量小，那么我们应该给多出来的流出量一个流出去的地方。所以就将点\(i\)向汇点T连一条容量为\(-...

题目链接 思路 既然是异或预算，很容易想到按位操作。 按位操作之后，每个点的权值就只有\(0\)和\(1\)两个了，然后从\(S\)向所有权值为\(0\)的点连一条\(INF\)的边，从所有权值为\(1\)的点向\(T\)连一条\(INF\)的边。然后将原图中的边全都连成权值为\(1\)的边。然后求最小割。 如果没有不确定的点权，那么很明显这样是对的。 画出图来就可以知道，对于不确定的点权这样操作也是对的。 这样就可以完成第一问了。 然后考虑第二问。在满足最小割的情况下要求点权最小。也就是说。再使得最小割不变的情况下，每个点的权值尽量的为\(0\)，也就是说尽量的割掉与\(T\)的连边。这...

问题 \(01\)分数规划是用来解决这样一类问题 有\(n\)个物品，每个物品都有一个属性\(p\)和\(w\)。要从中选出\(K\)个物品使得\(\frac{\sum\limits_{i=1}^Kp_i}{\sum\limits_{i=1}^Kw_i}\)最大，输出最大值。要求是个分数 思想 首先二分一个答案\(x\)。 然后将上面的问题转化为要选\(K\)个物品使得\[\frac{\sum\limits_{i=1}^Kp_i}{\sum\limits_{i=1}^Kw_i} \geq x\] 即\[\sum\limits_{i=1}^Kp_i-\sum\limits_{i...

题目链接 思路 如果想消灭掉一个植物，那么必须先消灭掉左右能保护这个植物的植物。这就成了最大权闭合子图的模板题了。 有两个需要注意的地方。 第一个就是，能保护当前植物的植物还有当前植物右面的所有植物。 第二个就是，在环里的植物或者是被在环里的植物所保护的植物是无法消灭的。 所以先拓扑一下，找出所有可能被消灭的植物，然后按照最大权闭合子图的做法做就行了。 代码 #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime>...

题目链接 题意 这个题首先要理解好题意，就是说给这个长方体横着切开。要求相邻的两个位置切点的为值不能相差大于\(D\)。 说的再直白一点就是。有一个\(P\times Q\)的矩阵，要在这\(P \times Q\)个格子里填区间\([1,R]\)中的数字。位置为\((x,y)\)的格子填\(z\)会有\(p(x,y,z)\)的代价。同时相邻的格子里填的数字之差不能超过\(D\)。求出最小代价。 思路 因为是要求最小代价，很容易想到最小割。 先考虑没有"相邻数字之差不能超过\(D\)"的限制应该怎么做。 这个很简单，我们可以把每个格子看成一条长度为\(R\)的链，从...

题目链接 思路 从源点\(S\)向每种药连一条边权为\(-p+inf\)的边。从每种药向他所需要的药材连一条边权为\(INF\)的边。从每种药材向汇点\(T\)连一条边权为\(inf\)的边。 \(INF>inf\) 用最小割减去源点连向药材的边权之和。 代码 #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<queue> #include<cmath> #include<ctime> ...

题目链接 思路 先将题目转化为求最小割。也就是要找出一些贡献不选，使得这些贡献的和最小。 对于单个点的贡献。显然我们可以从\(S\)到这个点连一条容量为选文收益的边。从这个点到\(T\)连一条容量为选理收益的边。 然后考虑哪些额外的贡献。只要相邻的这\(5\)个点中有任何一个不选文，那么这个集合选文的额外贡献就没有了。所以就新建一个点。然后从新建的这个点向这个集合中的\(5\)个点各连一条容量为\(INF\)的边，然后从\(S\)向这个新建的点连一条容量为贡献的边。对于理科同理。 然后跑一遍最小割，用总收益减去最小割即可。 代码 #include<cstdio> #incl...

题目链接 思路 这道题对于题意的转化很关键。 题目要求的是添上一条边，使得图中最大团的大小变大。给出的边是原图的补集，这就给我们了提示。 因为题目中说，原图中最多有两个团。所以给出的边一定形成了一个二分图。 那么最大团就是新图中的最大独立集。 那么问题就转化成了，在新图中删除一条边，使得新图中的最大独立集变大。 因为最大独立集 = 点数-最大匹配。 所以我们要让最大匹配变小。 考虑删除哪些边会让最大匹配变小。首先肯定要在跑完网络流之后是满流的。然后不能由其他的边来代替。也就是说在残余网络上跑一遍\(tarjan\)，满足两段不在同一个强联通分量中的边。 所以做法也就出来了。先建图跑一遍网络...

题目链接 题意 给出\(n\)个字符串，要构造一个长度为\(m\)的字符串\(S\)，使得给出的\(n\)个字符串中至少有一个是\(S\)的子串。问方案数。 思路 \(AC\)自动机+\(DP\) 考虑至少有一个是S的子串不好考虑。考虑用全部情况减去其中不包含任何一个字符串的情况。 全部情况就是\(26^m\)，然后考虑怎么求出不包含任何一个字符串的情况。 用\(f[i][j]\)表示已经确定了\(i\)个字符，现在到了\(AC\)自动机的j位置的方案数。 显然如果\(j\)位置是给出字符串的结尾或者沿着\(fail\)指针可以跳到给出字符串的结尾，那么就不能转移。其他的就可以转移到\...

题目链接 思路 可以发现，其实题目中所描述的操作，就是在\(AC\)自动机上走的过程。输出就是打上标记。删除就是返回父亲节点。 然后看询问。每次询问字符串\(x\)在字符串中\(y\)出现的次数。其实也就是问在\(AC\)自动机上的\(y\)这个字符串上，有多少位置的\(fail\)指针指向\(x\)的结尾。 所以想到将\(fail\)指针反过来，建立\(fail\)树。 先考虑只有一次询问的时候怎么做。只要将\(AC\)自动机上从根到\(y\)路径上的点在\(fail\)树上对应的变成\(1\)。然后询问以\(fail\)树上以\(x\)为根的子树有多少个\(1\)。 对于多次询问，可以...

题目链接 题意 给出一个\(n\)个字符串的字典。对于一个字符串，他的贡献是这个字符串中最多的在字典中出现的不重叠子串的数量。 然后问一个长度为\(len\)的，字符集为前\(alphabet\)个字符的字符串的贡献期望是多少。 思路 首先想如果这个长度为\(len\)的字符串已经给出了。应该怎么算贡献。 只要贪心的在\(AC\)自动机上走，如果走到了字典中字符串的结尾，就回到根节点，然后重新走。 现在没有给出这个字符串，在\(AC\)自动机上表现为每个点的每个儿子都有\(\frac{1}{alphabet}\)的概率存在。 这个题要求求期望，根据期望的线性性。只要求出每个字符串被经过...

题目链接 思路 观察题目中的式子，可以发现前两项是定值。所以只需要求出最后一项就行了。 然后题目就转化为了求字符串中所有后缀的\(lcp\)长度之和。 可以想到用后缀数组。在后缀数组上两个后缀的\(lcp\)长度表现为两个后缀排名之间的\(height\)的最小值。 所以现在问题就又转化为了在\(height\)数组上求所有区间最小值之和。 这个可以用单调栈做到。 代码 /* * @Author: wxyww * @Date: 2019-01-30 19:14:49 * @Last Modified time: 2019-01-30 20:49:38 */ #include<...

题目链接 题意 其实转化之后的题意就是求出树上有多少条路径长度是3的倍数。求答案的时候只要将这个数字除以总路径数量就行了。 思路 考虑点分治。对于当前子树，分别求出出树中每个点到根的路径长度对\(3\)取余后为\(0，1，2\)的个数。然后就可以通过\(0-0，1-2\)组合的方式，统计出答案。 然后删除当前点，继续递归下一层子树。 luogu数据较水，不找重心也能水过。 代码 /* * @Author: wxyww * @Date: 2019-01-30 10:56:53 * @Last Modified time: 2019-01-30 11:40:39 */ #inclu...