网络流小练

· · 个人记录

A

题意：给定两棵树，形态不同，编号为i的点价值为v_i。

第一棵树有P个限制，表示以a节点为根的子树中有选中b个节点

第二棵树有Q个限制，表示以a节点为根的子树中有选中b个节点

并且两棵树上的节点要么同时选要么同时不选

问是否存在一种构造方案，以及最大价值。n,P,Q\leq 500

神奇的网络流：

首先左边一排第一棵树的限制，每个点连向它子树内的所有节点；右边同理

为了保证每个节点只能选一次，所以要拆点限制1次

但是这样会有问题：就是最大流不代表所有的限制都已经满足了

因为这个限制关系具有传递性，所以如果p的某个儿子q已经满足了k_q的限制，那么p只需要在它的基础上多满足k_p-k_q个就可以了

所以维护一下每个子树中特殊限制的多少就可以了

B

给定n,m以及Q个限制，问是否存在集合满足：

首先弄出五个点表示取模的限制，连向所有模5为当前这个点的

然后考虑最后一个限制，其实和上一题几乎一样，只不过树上变成了区间上

同样限制关系在前缀上具有传递性，差分一下就好了

C

题意：给定一个n\times m的矩阵，要从S走到 T，每次移动可以移动到一行或一列中任意一个o的位置，不能走到.的位置。问最少把多少个.改成o使得无法从S走到T

n,m\leq 100

每一行、每一列弄出一个虚拟点，然后跑最小割就行了

D

有n个学生和m个社团，每个学生有一个能力值并且属于一个社团

每一天都有一个学生离开他所在的社团，并且每一天需要从每一个不为空的社团中选出一个学生组成代表团

一个代表团的权值为里面所有学生权值的\rm mex，最大化每天代表团的权值

n,m\leq 5000

首先时间倒流，变为每天有学生加入

如果一个代表团的权值为{\rm mex}=x，那么1\sim x-1权值肯定都已经有了

所以可以考虑动态一个一个权值加入，那么每个学生相当于边，连接权值和社团

只要当前最大流等于加入的权值点个数，那么就是合法的，让答案加1即可

考虑到加入一个学生不会让答案变劣，所以每一天枚举的答案从上一天开始就行

注意到这只是一个二分图，并且每次需要判断一个点是否能找到一个匹配的点，所以直接用二分图匹配

E

题意：给定一个DAG，每条边有边权，给每个点标号。一条边x\to y对答案的贡献为(a_y-a_x)\times val(x\to y)，并且要满足a_y>a_x

最小化代价，n\leq 18

可以用网络流，但只会状压

显然尽可能让每条边都是1是最优的， 但这不一定能满足

那么问题就相当于：给每个点安排一个层数，一条边的贡献就是边权乘上两端点层数的差

设当前S状态的点已经安排好了，此时新加入T状态的点，那么首先要满足：\forall y\in T,(x,y)\in E\to x\in S

那么如何计算贡献呢？如果一个点a\in S，点b\in S，且(a,b)\in E，那么(a,b)就会对答案有至少一次贡献

如果在T的时候b就选上，会有一次的贡献，如果在下下次选上就会有两次贡献；所以每次都加入还没有进入被选集合的贡献，提前计算即可

F

题意：给定一个长度为m的空书架，有n个请求：

第i个请求，表示此时需要有a_i这本书，如果书架上有这本书可以忽略这个请求；不然就需要花cost[a_i]去购买这本书放到书架上。

在任意时刻都可以扔掉书架上任意一本书，最小化花费

1\leq n,m\leq 80

一流对多流模型：

考虑一本书在i,j(i<j)两个位置都出现了，那么有两种策略：

在i或i之前已经有了这本书，然后一直放在书架上给j需求用；在(i,j)这段时间把这本书扔掉，然后在j时买回来

因为要扔掉所以肯定越早越优，所以直接在i+1就扔掉就好了

考虑到如果不扔掉，那么就要在书架上占位置

所以一开始先把所有的书买进来，然后对于一本书相邻出现的位置(i,j)，如果我们选择把它留下来，那么它在[i+1,j]肯定会占用一个位置，但是就可以减掉代价了

所以直接连边(i+1,j)，费用为这本书的价格，然后跑最大费用流，总的价格减去跑出来的费用

根据网络流的最优性，它就会选择是把这本书留在书架上减去价格，还是把它扔掉不占用位置

G

并不是网络流，而是一道伪装计数的以为是贪心的博弈论FWT

AT5800 [AGC043C] Giant Graph

H

I是这题的弱化版，所以只写这题

题意：给定一个数组，选出4个子序列，每个子序列内部相邻两个元素满足：差值为1或者对7取模相同

问最多能取多少个元素，n\leq 5000

每个点只能选一次，所以先拆开来，一个表示入一个表示出，中间放一条限制为1的边

每个出点就要连向下一个差为1或者对7取模相同的

但因为到下一个不一定要选，也可以继续往下走，所以一个点拆成4个：(a,b,c,d)

a$表示值的“等价类”，连向下一个值相同的以及$c b$表示模的“等价类”，连向下一个模相同的以及$c $d$表示取了这个后下一个去哪里，连向下一个差值为$1$的$a$，以及模数相同的$b

跑一个最大费用流即可