网络流 24 - 1 题
负载平衡问题
贪心
环形均分纸牌，首先有很典的贪心，吊打网络流。
设 \(d_i\) 表示 \(i\) 向 \(i \bmod n + 1\) 传递的数量，\(aver = \dfrac{\sum_{i = 1} ^ {n} a_i}{n}\)，那么有：
\[\begin{cases}
aver = a_1 - d_1 + d_n \\
aver = a_2 - d_2 + d_1 \\
\dots \\
aver = a_n - d_n + d_{n - 1}
\end{cases}
\]
代入消元，可得通项公式 \(d_i = \sum_{j = 1} ^ {i} a_j - j \times aver + d_n = d_n - \sum_{j = 1} ^ {i} (aver - a_j)\)。
这个明显可以前缀和，设 \(s_i = \sum_{j = 1} ^ {i} (aver - a_j)\)，那么最终答案 \(\sum_{i = 1} ^ {n}\left\vert d_i \right\vert =\sum_{i = 1} ^ {n} \left\vert d_n - s_i \right\vert\)，显然 \(d_n\) 取中位数最优。
费用流
首先建立源点和汇点 \(s, t\)， \(s\) 向每个仓库连容量为 \(a_i\)，费用为 \(0\) 的边，每个仓库向 \(t\) 连容量为 \(\bar{a}\) ，费用为 \(0\) 的边。然后相邻仓库之间连容量为 \(+\infty\)，费用为 \(1\) 的边。跑费用流即可。这个非常直观。