题解 P7246 【手势密码】
Elegia
·
·
题解
懒得推贪心咋做啊？
我们考虑将问题描述为线性规划，设集族 \mathcal I 包含了所有的路径，那么我们无非要给每条路径 S 赋予一个权值 x_S 表示这条路径走了多少次，容易写出约束：
\forall u, \sum_{S\ni u} x_S=a_u
我们的目的就是最小化
\sum_{S\in \mathcal I} x_S
线性规划一般是用不等式表述的，所以我们先将前面的等式拆成两组不等式，就可以写成标准的形式：
\begin{matrix}
& x_S \ge 0,\\
\mathrm{minimize} & \sum_{S\in \mathcal I} x_S, \\
\mathrm{s.t.} & \sum_{S\ni u} x_S &\ge & a_u & (s_u)\\
& \sum_{S\ni u} -x_S &\ge& -a_u & (t_u)\\
\end{matrix}
我们改写为其对偶线性规划，即变成
\begin{matrix}
& s_u,t_u \ge 0,\\
\mathrm{maximize} & \sum_u a_u(s_u-t_u), \\
\mathrm{s.t.} & \sum_{u\in S} (s_u-t_u) &\le & 1 & (x_S)\\
\end{matrix}
不难看出，我们可以令 b_u=s_u-t_u，那么就相当于 b_u 可任取，然后目标是最大化 \sum a_ub_u，满足约束
\forall S\in \mathcal I,\sum_{u\in S} b_u \le 1
根据线性规划的对偶定理，这两个问题的解是相等的，我们只需求解后者。
由此，我们可以自然地设计一个 DP：f_{u,d} 表示 u 这颗子树里从 u 出发，b 值之和最大的路径为 d 时最大的 \sum a_ub_u。显然 d \in \{0,1\}。而 b_u 只有三种必要的取值：\{-1,0,1\}。我们枚举各情况进行转移，即是一个 \Theta(n) DP。
（不过这里有一个小疑点，就是为什么最优解一定是整数。容易发现本题的约束矩阵并不是全幺模的，因此不能套用该充分条件来说明。）