#P8374. [ioi2018国家队集训]拆分

    ID: 8461 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>图论贪心动态规划CF2400二分图构造DFS数学

[ioi2018国家队集训]拆分

拆分(divide)

题目背景

由于经营不善,DT 航空倒闭了。

现在有 k 个人打算尽量平分掉 DT 航空的财产。

题目描述

A 国有 nA 个城市,B 国有 nB 个城市。

DT 航空经营 m 条 A 国到 B 国的航线。

第 ii 条航线连接 A 国的第 xix_i 个城市和 B 国的第 yiy_i 个城市。所有端点编号均在各自城市编号范围内。 现在你需要将 m 条航线分配给 k 个人,并且分的尽量平均。 定义 w_ij 为经过第 i 个城市的分配给第 j 个人的航线数量。

定义城市 i 的不平均度为 max{w_ij}-min{w_ij},j∈[1,k]。 定义一个方案的不平均度为 nA+nBn_A+n_B 个城市的不平均度之和。 现在你需要求出不平均度最小的方案。

输入格式

第一行四个整数 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

对于所有数据,nA,nB≤300n_A,n_B\le300,1≤k≤3001\le k\le300,m/k≤300m/k\le300。无需假设人数不超过城市数或航线数:若某人在某城市没有航线,对应计数为0;没有航线的城市不平均度为0。

数据保证没有两条完全相同的航线。

任意一个满足不平均度最优的方案均正确。

出题人下发了一个 checker。