Description

Berland 和 Beerland 之间有发达的航班网络,它们都属于 Berland 国营公司 BerAvia。每条航线将 Berland 的一个城市和 Beerland 的一个城市连接起来。

最近,Berland 决定私有化 BerAvia,他们将航线卖给了 $k$ 家私人公司。这些公司希望航线的划分尽量均匀。

具体地,对每个城市 $i$,定义不均匀度

$$w_i=\max_j a_{i,j}-\min_j a_{i,j}$$

其中,$a_{i,j}$ 代表公司 $j$ 拥有的经过 $i$ 市的航线数量。

Berland 政府希望不均匀度的平均值最小,请帮助它们找到最佳方案,并输出不均匀度的和。

Idea

这道题可以跑网络流但是我不会。

我们将每个城市拆分成数目最少的点,使得每个点的度数 $\leq k$。对于新图,做二分图最小边染色即可,可以证明二分图最小边染色数 $=\max \text{Degree}$。具体地,我们利用一个类似匈牙利的算法实现。

设 $f_{i,j}$ 代表新图上从 $x$ 点出发,颜色为 $j$ 的边另一个端点的编号。每次新加入一条从 $x$ 到 $y$ 的边时,找到这两个端点可以使用的最小颜色编号,分别设为 $cx,cy$。如果 $cx=cy$,可以直接加边;否则,我们要为 $y$ 端点处占用了 $cx$ 的边更换颜色。具体地,我们可以找到一条从 $y$ 出发的,颜色为 $cx,cy$ 交替出现的增广路,将这条增广路上的 $cx,cy$ 互换。

这样做的时间复杂度为 $\Theta(\frac{m^2}{k}+mn)$。

Code