题面下载（加密）：20191206.zip

buniss

30分算法

考虑费用流。建图方式如下：

• 源点向树上的点 i 连一条容量为 a_i ，费用为 0 的边；
• 每个果粉对应的链上的点向这个果粉连一条容量无穷大，费用为 0 的边； 果粉 i 向汇点连一条容量为 c_i ，费用为 s_i 的边。 跑最大费用最大流即可。

70分算法

有一个明显的思路是把果粉按 s_i 从大到小排序，这样答案就是在第一个人选的苹果数量最大的情况下最大化第二个人选的，在第二个人选的苹果数量最大的情况下最大化第三个人选的，以此类推。假设我们现在正在处理第 i 个人，考虑二分他最多选的苹果的个数。将果粉和果树建立映射关系，由霍尔定理可知，对于每个果粉的子集，这个子集中的人期望要选的苹果个数之和（设为 A）应不大于他们能选的果树上的苹果个数之和(设为 B) ，即 A-B\leq 0。不包含第 i 个人的子集一定是符合的，因为之前已经验证过了。考虑 DP ，f(i,j) 表示考虑链的末端在子树 i 中，顶端在 i 的第 j 个祖先下的人组成的子集的 A-B 的最大值。最后判断 max(f(1,0),f(1,1)) 是否小于等于 0 即可。 每次二分都会重新计算 v_i 到根这些节点的 DP 状态，共 O(\log^2n) 个，因此复杂度为 O(m\log^3n) .

100分算法

这部分我也没有想清楚。。大致是令 g(i,j)=0/1 表示强制令这个状态不选/选，然后直接 DP 似乎就能得到答案了（ 还有一种思路是基于费用流改进的模拟费用流算法，但是我并不会。。

farcue

10分算法

n=1 的情况，若 m 为奇数直接无解，否则将第一个数随便指定一个再依次推下去就可以了。证明不难。

30分算法

在上个算法的基础上加入 n=2 的部分。将每一列数两两配对，每一对的和的下界都是有限的，所以一定有解。将第一行第一列的数任意指定后同样依次推下去就可以了。

100分算法

因为网格图是二分图，有一个结论是答案一定是一个最大匹配（证明不会） 状压 DP 求出最大匹配。输出解则考虑差分约束

建好图后我们需要求出点 (1,1) 到其他所有点最短路。由于