ARC 089 C

肯定想到要看看 \(x,y\) 用的个数，那么推柿子。如果设 \(f_{i,j}\) 为 \(S\rightarrow T\) 中必须包含 \(i\) 个 \(\text{X}\) 和 \(j\) 个 \(\text{Y}\) 的其他边权的最小和。那么 \(d_{x,y}=\min(f_{i,j}+ix+jy)\)。因为我们已知的是 \(d\)，未知的是 \(f\)，因此尝试移项（考虑 \(f_{i,j}+ix+jy\) 贡献给的 \(d_{x,y}\)），那么 \(f_{i,j}=\max(d_{x,y}-ix-jy)\)。

现在我们可以求出所有 \(f\)，并且带回去看看合不合法。尝试构造方案。

因为有“必须包含 \(i\) 个 \(\text{X}\) 和 \(j\) 个 \(\text{Y}\)” 这种，因此先弄两个链，一个链上面全部是 \(\text{X}\)，一个上面全部是 \(\text{Y}\)。\(f_{i,j}\) 可以看作是两边的桥梁。\(S\) 和 \(T\) 分别是两边的链头链尾。