#P8374. [ioi2018国家队集训]拆分
[ioi2018国家队集训]拆分
拆分(divide)
题目背景
由于经营不善,DT 航空倒闭了。
现在有 k 个人打算尽量平分掉 DT 航空的财产。
题目描述
A 国有 nA 个城市,B 国有 nB 个城市。
DT 航空经营 m 条 A 国到 B 国的航线。
第 条航线连接 A 国的第 个城市和 B 国的第 个城市。所有端点编号均在各自城市编号范围内。 现在你需要将 m 条航线分配给 k 个人,并且分的尽量平均。 定义 w_ij 为经过第 i 个城市的分配给第 j 个人的航线数量。
定义城市 i 的不平均度为 max{w_ij}-min{w_ij},j∈[1,k]。 定义一个方案的不平均度为 个城市的不平均度之和。 现在你需要求出不平均度最小的方案。
输入格式
第一行四个整数 nA,nB,m,k,含义同题目。
接下来 m 行,一行两个数 x_i,y_i,表示一条航线。
输出格式
一行 m 个数字表示答案。
第 i 个数字为 x 表示第 i 条航线被划分给第 x 个人。
样例输入1
3 5 8 2
1 4
1 3
3 3
1 2
1 1
2 1
1 5
2 2
样例输出1
2 1 2 1 2 1 2 2
数据范围
| 测试包编号 | nA,nB<= | k<= | 分值 |
|---|---|---|---|
| Subtask 1 | 5 | 10 | |
| Subtask 2 | 300 | 2 | 20 |
| Subtask 3 | 3 | 15 | |
| Subtask 4 | 15 | 25 | |
| Subtask 5 | 300 | 30 | |
对于所有数据,,,。无需假设人数不超过城市数或航线数:若某人在某城市没有航线,对应计数为0;没有航线的城市不平均度为0。
数据保证没有两条完全相同的航线。
任意一个满足不平均度最优的方案均正确。
出题人下发了一个 checker。