题解：CF2046D For the Emperor!

· · 题解

凭啥 3k1 来着。

首先显然要缩点成一个 DAG，每个点的 a 是 SCC 里所有的 a 之和，然后考虑网络流。

一条一条限制看，首先点 u 能派出的信使个数 \operatorname{out}(u) 与到达点 u 的信使个数 \operatorname{in}(u) 必然有：

\operatorname{out}(u)\le \operatorname{in}(u)+a_u

然后每个点都必须要有至少一个信使经过，那么就把点 u 拆成 u_{\text{in}} 和 u_{\text{out}}，连一条 u_{\text{in}} 到 u_{\text{out}} 的下界为 1，上界为 +\infin 的边。

考虑什么时候要单独给 u 一份计划，当且仅当入流量为 0，也就是说，没法满足 u_{\text{in}} 到 u_{\text{out}} 的下界。开一个新点 u_{\text{mid}}，向 u_\text{in} 连一个上界为 1，费用为 1 的边，向 u_{\text{out}} 连一条上界为 +\infin 的边。

结合第一条限制，s 再向 u_\text{mid} 连一条上界为 a_u 的边，因为信使可以在任何一个站点停下，所以再从 u_{\text{out}} 向 t 连一条上界为 +\infin 的边。

然后直接最小费用上下界可行流。