题意
给定 $n, b, s, r$。
有 $n$ 个点，$r$ 条边的有向图，边有边权，表示通信成本。编号为 $b + 1$ 的点是中转点，任意两点发送信息都要先送到 $b + 1$，再由 $b + 1$ 送到目标点。
你要把前 $b$ 个点任意分成 $s$ 组，每组里的任意两个点都要互发消息。
总代价为所有组的通信成本之和。
求出最小可能的总代价。
$2 \leq n \leq 5000$
题解
设 $x \to y$ 表示 $x$ 向 $y$ 发送信息的通信成本。
若 $a$ 与 $b$ 要互发消息，那么代价为：
$$a \to p + p \to b + b \to p + p \to a$$
其中 $p$ 就是中转点。
我们移项：
$$a \to p + p \to a + b \to p + p \to b$$
于是我们设 $t_a = a \to p + p \to a$。
一个大小为 $s$ 组 $S$ 里的通信成本可以表示为：
$$\left(s - 1\right) \sum\limits_{i \in S} t_i$$
于是我们希望让 $t_i$ 小的点聚在一起，凑一个大小比较大的组，然后让 $t_i$ 较大的点聚在一起，凑一个大小比较小的组。
于是我们把 $t_i$ 从小到大排序。
于是我们得到一个 $\mathcal O\left(b^2s\right)$ 的 DP：
设 $f_{i, j}$ 表示前 $i$ 个点分为 $j$ 组的最小成本。
$$f_{i, j} = \min\limits_{k < i}f_{k, j - 1} + cost\left(k + 1, i\right)$$
注意到我们分组的大小是单调不减的，因为我们希望让 $t_i$ 小的点聚在一起，，然后让 $t_i$ 较大的点聚在一起。
于是第 $j$ 个组的大小不会超过 $i / j$，于是复杂度是 $b$ 乘上一个调和级数。
于是总复杂度是 $\mathcal O\left(bs \log b\right)$。
代码
// :/
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp n, b, s, m; bin >> n >> b >> s >> m;
vector<vector<PTT>> e(n + 1), fe(n + 1);
while (m--) {
tp u, v, w; bin >> u >> v >> w;
e[u].emplace_back(v, w);
fe[v].emplace_back(u, w);
}
vector<vector<tp>> f(n + 1, vector<tp>(s + 1, INF));
auto p_to_all = lib::Dijkstra(e, b + 1);
auto all_to_p = lib::Dijkstra(fe, b + 1);
vector<tp> self(b + 1);
for (tp i = 1; i <= b; ++i) self[i] = all_to_p[i] + p_to_all[i];
stable_sort(1 + FULL(self));
vector<tp> ps_self(b + 1);
for (tp i = 1; i <= b; ++i) ps_self[i] = ps_self[i - 1] + self[i];
for (tp i = 1; i <= b; ++i) f[i][1] = (i - 1) * ps_self[i];
for (tp i = 2; i <= b; ++i) {
for (tp j = 2; j <= min(i, s); ++j) {
for (tp k = i - i / j; k < i; ++k) {
f[i][j] = min(f[i][j], f[k][j - 1] + (i - k - 1) * (ps_self[i] - ps_self[k]));
}
}
}
bin << f[b][s] << '\n';
return 0;
}
void MIST() {
}
// :\ */