洛谷 P6122
模拟费用流
首先建模是比较简单的，\(s\) 向每个鼠的位置连一条流量为 \(1\)，费用为 \(0\) 的边，每个点向 \(t\) 连一条流量为 \(c_i\)，费用是 \(0\) 的边，树上的边直接连双向边，流量为 \(+\infty\)，费用为 \(1\)。跑最小费用最大流即可。
模拟费用流模拟的是求最短路的过程，然后单路增广。
假设当前鼠的位置为 \(u\)，一定是先向上走到某个点 \(lca\)，再向下走到 \(v\)，进而走到 \(t\)。因为树高只有 \(O(\log n)\)，可以直接枚举 \(lca\)，求出 \(u \rightarrow lca\) 的代价。所以只需要找到从 \(lca\) 出发花费最小代价能到达的 \(v\) 且 \(v, t\) 之间还有流量。
这个可以直接使用 DP 维护，令 \(dp(u)\) 表示上面说的东西，那么 \(dp(u)\) 可以从 \(dp(2u), dp(2u + 1)\) 转移，当然如果 \(u, t\) 之间有流量就是 \(0\)。
这里说一下如何求走一条路径的代价。对与一条路径上的每条边，计算经过它的代价。因为有反悔边的存在，代价并不是 \(1\)，而是 \(1/-1\)。具体的假设从上往下走，如果此前这条边从上往下走的次数少于从下往上走的次数，那么就进行反悔，代价为 \(-1\)，否则就是 \(1\)。从下往上走同理。所以只需要维护这条边走的次数 \(c(e)\) 即可。
找到代价最小的路径后增广，修改沿途中的 \(c(e)\)，同时维护 \(dp(u)\)（只需要更新 \(u, v\) 到根的）即可。
时间复杂度：\(O(n \log n)\)。
模拟费用流一般难点不在于建模，而是找出最短路。