D. 为了皇帝！ 详细题解

问题重述

给定一个 $n$ 个节点、$m$ 条有向边的图，每个节点 $i$ 有 $a_i$ 个信使（$0 \le a_i \le n$）。信使可以沿有向边移动，可以在到达的城市无限复制计划给其他信使。初始时你可以选择一些信使，给他们一份计划。目标：最终每个城市都至少被一个携带计划的信使访问。求最少需要初始发放计划的数量，或判断不可能（输出 $-1$）。

关键观察

1. 强连通分量内部：在一个强连通分量（SCC）内，信使可以到达分量内任意节点。因此，只要分量内至少有一个信使获得计划，整个分量的所有城市都可以被覆盖。
2. 缩点后的 DAG：将原图缩点为 SCC 得到有向无环图（DAG）。每个 SCC 视为一个节点，其内部信使数量为分量内所有城市的信使数之和 $a_{\text{comp}}$。
3. 问题转化：在 DAG 上，我们需要选择一些 SCC 作为“起始点”，使得从这些起始点出发，沿着有向边可以到达所有 SCC。每个起始点需要消耗一个计划（即给该分量内的某个信使一份计划）。但每个 SCC 可能有多个信使，我们可以选择不使用额外计划而依赖其他分量的信使传递进来。

网络流建模思路

我们要最小化初始发放计划的数量，等价于在 DAG 上找最少的“源”节点，使得所有节点都能被到达，并且每个节点 i 最多允许从它的信使中派出 $a_i$ 条路径（每条路径对应一个信使传递计划的过程）。

标准解法是使用最小费用最大流（MCMF），构造一个流网络，使得流量代表计划传播的路径，费用代表我们主动发放的计划数量。

缩点与建图步骤

设缩点后共有 $C$ 个 SCC，编号 $0 \dots C-1$。记 $A[i]$ 为第 $i$ 个 SCC 的总信使数。

1. 基本流网络（判断可行性）

首先考虑是否存在一种方案使得所有 SCC 都能被覆盖（不管初始计划数量）。这等价于：能否在 DAG 上找到若干条路径，覆盖所有节点，且每个节点 $i$ 出发的路径数不超过 $A[i]$（因为每个信使只能带一份计划出发，但可以在途中复制，所以出发路径数受限于初始信使数）。

经典构造：

• 将每个 SCC $i$ 拆成两个节点 $i_{in}$ 和 $i_{out}$，中间连一条边 $i_{in} \to i_{out}$，容量为 $\infty$，并强制这条边至少流过 $1$（表示该 SCC 至少被一条路径覆盖）。
• 添加源点 $s$ 和汇点 $t$，从 $s$ 到 $i_{in}$ 连容量 $A[i]$ 的边（表示从该 SCC 最多派出 $A[i]$ 条路径）。
• 从 $i_{out}$ 到 $t$ 连容量 $\infty$ 的边。
• 对于原 DAG 中的边 $i \to j$，从 $i_{out}$ 到 $j_{in}$ 连容量 $\infty$ 的边。
• 强制 $i_{in} \to i_{out}$ 的流量至少为 $1$，这可以通过将这条边拆分为：保留容量 $\infty-1$，并增加一个辅助源汇强制流 $1$（见下文）。

2. 转化为标准流问题

为了处理“至少 $1$”的约束，引入两个虚拟节点 $s'$ 和 $t'$：

• 对每个 $i$，从 $i_{in}$ 到 $i_{out}$ 连容量 $\infty-1$ 的边（可理解为除了必须流的 $1$ 之外还能多流）。
• 再从 $s'$ 到 $i_{out}$ 连容量 $1$ 的边。
• 再从 $i_{in}$ 到 $t'$ 连容量 $1$ 的边。
• 最后，从 $t$ 到 $s$ 连容量 $\infty$ 的边（形成循环流）。

这样，从 $s'$ 到 $t'$ 的最大流若等于 $C$，则说明每个 SCC 都至少被一条路径覆盖，即存在可行方案。若最大流小于 $C$，则输出 $-1$。

3. 最小化初始计划数（最小费用）

在上述网络中，若从 $s$ 到 $i_{in}$ 的边每条流量代表一个信使从该 SCC 出发。我们想要最小化“主动发放计划”的数量，即那些没有从其他 SCC 获得计划、必须自己初始拥有的信使数。

在原网络中，每个 SCC 内的信使可以：

• 要么被其他 SCC 传来的计划“激活”（即该 SCC 的 $i_{in} \to i_{out}$ 边上的流量来自入边，而非从 $s$ 出发），此时该 SCC 不需要主动发放计划；
• 要么自己作为源头，即从 $s$ 到 $i_{in}$ 的边上产生流量，此时需要消耗一个计划（因为要分给该 SCC 的一个信使）。

为了计算最小计划数，我们给从 $s$ 出发的边赋予费用 $1$，其他边费用为 $0$，然后求从 $s'$ 到 $t'$ 且流量恰好为 $C$ 的最小费用最大流。但注意，从 $s$ 到 $i_{in}$ 的边容量为 $A[i]$，但每次激活该 SCC 可能不需要用满所有信使，我们只需至少有一条路径经过该 SCC。实际上，我们可以在每个 SCC 内部再增加一个中间节点 $i_{cnt}$ 来控制费用。

更精确的构造（标程实现）：

• 为每个 SCC $i$ 创建三个节点：$i_{in}$、$i_{out}$、$i_{cnt}$。
• 连边：
  • $s \to i_{cnt}$，容量 $A[i]$，费用 $0$。
  • $i_{cnt} \to i_{in}$，容量 $1$，费用 $1$（表示若该 SCC 作为源点，则花费 $1$）。
  • $i_{cnt} \to i_{out}$，容量 $A[i]$，费用 $0$（表示信使可以直接流向 $i_{out}$，不消耗计划，但这样会导致没有经过 $i_{in} \to i_{out}$ 的强制流，需要配合其他边）。
  • $i_{in} \to i_{out}$，容量 $\infty$，费用 $0$。
  • $i_{out} \to t$，容量 $\infty$，费用 $0$。
• 添加 $s' \to i_{out}$，容量 $1$，费用 $0$；$i_{in} \to t'$，容量 $1$，费用 $0$。
• 添加 $t \to s$，容量 $\infty$，费用 $0$。
• 对于原 DAG 边 $i \to j$：$i_{out} \to j_{in}$，容量 $\infty$，费用 $0$。

此时，从 $s'$ 到 $t'$ 的流量 $C$ 表示每个 SCC 都被经过一次（强制流）。而 $s$ 到 $i_{cnt}$ 的流量中，通过 $i_{cnt} \to i_{in}$ 的那 $1$ 个单位流量需要支付费用 $1$，表示该 SCC 需要主动发放一个计划；通过 $i_{cnt} \to i_{out}$ 的流量则不需要费用，但无法满足强制流（因为强制流要求经过 $i_{in} \to i_{out}$），因此实际上每个 SCC 必须有且仅有 $1$ 单位流量经过 $i_{in} \to i_{out}$，这 $1$ 单位要么来自 $s$ 通过 $i_{cnt} \to i_{in}$（费用 $1$），要么来自其他 SCC 的 $i_{out} \to i_{in}$（费用 $0$）。所以最小费用即为最少需要主动发放的计划数。

算法步骤

1. 对原图跑 Tarjan 或 Kosaraju 求 SCC，得到缩点后的 DAG。
2. 计算每个 SCC 的总信使数 $A[i]$。
3. 建立上述 MCMF 网络，节点数 $3C + 4$，边数 $O(C + m)$。
4. 运行最小费用最大流，从 $s'$ 到 $t'$ 求流量为 $C$ 的最小费用。
5. 若最大流小于 $C$，输出 $-1$；否则输出最小费用。

复杂度

• SCC 缩点：$O(n + m)$。
• 网络流：节点数 $\le 3 \times 200 + 4 = 604$，边数 $\le 2000$，使用 SPFA 或 Dijkstra 势能优化，流量值 $C \le 200$，复杂度 $O(\text{flow} \cdot m \log n)$ 可接受。

参考代码（标程已提供）

标程使用 Kosaraju 求 SCC，然后实现 MCMF（基于 SPFA 或类似算法）。代码中：

• getInd(i) 返回三个索引 (uin, uout, ucnt)。
• MCMF 类实现了最小费用最大流（使用类似 SPFA 的队列优化）。
• 建图过程完全对应上述描述。

总结

本题是典型的图论与网络流结合问题，核心是将信使传播建模为覆盖所有节点的路径集，通过拆点、强制流和费用边来最小化源点数量。利用 SCC 缩点简化 DAG，再使用 MCMF 求解，是解决此类问题的标准方法。