CF212A Privatization

在 Berland 和 Beerland 之间有一个发达的航班网络。所有航班均归属于 Berland 国有公司 BerAvia。每个航班连接 Berland 的某个城市与 Beerland 的某个城市。每班航班都是双向运营的。 Berland 即将进行改革——国家决定将 BerAvia 私有化，即将所有航班出售给 $ t $ 个私营公司。这些公司都希望获得最多的航班数量，因此如果航班分配不均，Berland 可能受到偏袒指控。为此，Berland 政府决定尽可能平均地将航班分配给 $ t $ 家公司。 航班分配的不均衡程度按如下方式计算。对于每个城市 $ i $（包括 Berland 和 Beerland 的城市），计算值  其中 $ a_{ij} $ 表示属于公司 $ j $、从城市 $ i $ 出发的航班数。所有城市的 $ w_i $ 值之和被称为分配的不均衡程度。分配的不均衡程度最小的方案就是最均匀的分配方案。请帮助 Berland 政府制定一个最均匀的航班出售方案。

第一行包含四个整数 $ n,m,k $ 和 $ t $（$ 1\leq n,m,t\leq200; 1\leq k \leq 5000 $），其中 $ n,m $ 分别表示 Berland 和 Beerland 的城市数，$ k $ 表示两国间航班总数，$ t $ 表示私营公司的数量。接下来的 $ k $ 行每行描述一班航班，每行两个正整数 $ x_i,y_i $（$ 1\leq x_i \leq n; 1\leq y_i \leq m $），表示第 $ i $ 个航班连接 Berland 的第 $ x_i $ 号城市与 Beerland 的第 $ y_i $ 号城市。任意一对城市之间最多只有一班航班，每班航班都连接不同国家的城市。Berland 的城市编号为 $ 1\sim n $，Beerland 的城市编号为 $ 1\sim m $。

输出一行表示所求方案的不均衡程度。第二行输出 $ k $ 个整数 $ c_{1},c_{2},...,c_{k} $（$ 1\leq c_{i}\leq t $），其中 $ c_{i} $ 表示第 $ i $ 个航班应被哪家公司的编号购买。假定航班编号按输入中的顺序从 $ 1 $ 到 $ k $。如果有多种方案，输出任意一种即可。

由 ChatGPT 5 翻译