[八省联考2018] 劈配 mentor (2)

在这一部分,保证每行中不存在某一个正数出现超过 C 次(0 可能出现超 过C 次),同时保证所有$a_{i,j}$ <= m。

第n + 3 行n 个用空格隔开的正整数,其中第i 个整数为$s_i$

$s_i$ 表示编号为i 的选手的理想值。

在这一部分,保证$s_i$ <= m。

Output

按顺序输出每组数据的答案。对于每组数据,输出2 行:

第1 行输出n 个用空格隔开的正整数,其中第i 个整数的意义为:

在最优的录取方案中,编号为i 的选手会被该档志愿录取。

特别地,如果该选手出局,则这个数为m + 1。

第 2 行输出 n 个用空格隔开的非负整数,其中第 i 个整数的意义为:

使编号为i 的选手不沮丧,最少需要让他上升的排名数。

特别地,如果该选手一定会沮丧,则这个数为i。

Range

[八省联考2018] 劈配 mentor

Solution

第一问可以优化,如果第 i 个人的第 j 级志愿不能增广,就直接把这些边删掉。

第二问只需要对于每一个人二分答案 $ans_i$ ,把 $ans_i$ 之前的人全部按照最优方案建出图,然后额外的连上第 i 个人所期望的边,再寻找增广路,就可以完美解决第二问。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzxxpd.html