[NOI2015] 小园丁与老司机
显然这是一个按 \(y\) 分层的无向图，第一问直接作 DP 即可。令 \(dp_{0/1, i}\) 表示 \(i\) 为这一层到达的第一个/最后一个点能许愿的树的最大值。
第二问直接倒推即可，有多种走法就随便选一个（注意 \(dp_{1, i}\) 可以从 \(dp_{0, i}\) 转移）。
第三问，要把所有可能的车辙求出来，然后跑上下界网络流（下界为 \(1\)，上界为 \(+\infty\)）。计算车辙可以和第二问一起做。记录每个点是否能到达一个最优答案。（\(dp_{0, i}, dp_{1, i}\) 都要记录。）
所有倒推分成层内部，和层之间的。
看起来思路简单，实际上代码一坨，写了好久。
时间复杂度略，因为容量都是一样的，还是很快的。