题目背景

一年一度的综艺节目《中国新代码》又开始了。Zayid 从小就梦想成为一名程序员,他觉得这是一个展示自己的舞台,于是他毫不犹豫地报名了。

题目描述

轻车熟路的Zayid 顺利地通过了海选,接下来的环节是导师盲选,这一阶段的规则是这样的:

总共n 名参赛选手(编号从1 至n)每人写出一份代码并介绍自己的梦想。接着 由所有导师对这些选手进行排名。为了避免后续的麻烦,规定不存在排名并列的情况。

同时,每名选手都将独立地填写一份志愿表,来对总共 m 位导师(编号从 1 至 m)作出评价。志愿表上包含了共m 档志愿。对于每一档志愿,选手被允许填写最多C 位导师,每位导师最多被每位选手填写一次(放弃某些导师也是被允许的)。

在双方的工作都完成后,进行录取工作。每位导师都有自己战队的人数上限,这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。节目组对”前i 名的录取结果最优“ 作出如下定义:

  • 前1 名的录取结果最优,当且仅当第1 名被其最高非空志愿录取(特别地,如 果第1 名没有填写志愿表,那么该选手出局)。
  • 前i 名的录取结果最优,当且仅当在前i – 1 名的录取结果最优的情况下:第i 名 被其理论可能的最高志愿录取(特别地,如果第i 名没有填写志愿表、或其所有 志愿中的导师战队均已满员,那么该选手出局)。

如果一种方案满足‘‘前n 名的录取结果最优’’,那么我们可以简称这种方案是最 优的。

举例而言,2 位导师T 老师、F 老师的战队人数上限分别都是1 人;2 位选手 Zayid、DuckD 分列第1、2 名。那么下面3 种志愿表及其对应的最优录取结果如表中所示:

qwq

我是图片qaq

可以证明,对于上面的志愿表,对应的方案都是唯一的最优录取结果。

每个人都有一个自己的理想值si,表示第i 位同学希望自己被第si 或更高的志愿录取,如果没有,那么他就会非常沮丧。

现在,所有选手的志愿表和排名都已公示。巧合的是,每位选手的排名都恰好与它们的编号相同。

对于每一位选手,Zayid 都想知道下面两个问题的答案:

  • 在最优的录取方案中,他会被第几志愿录取。
  • 在其他选手相对排名不变的情况下,至少上升多少名才能使得他不沮丧。

作为《中国新代码》的实力派代码手,Zayid 当然轻松地解决了这个问题。不过他还是想请你再算一遍,来检验自己计算的正确性。


输入输出格式

输入格式:

从文件mentor.in 中读入数据。

每个测试点包含多组测试数据,第一行 2 个用空格隔开的非负整数 TC,分别表示数据组数、每档志愿最多允许填写的导师数目。

接下来依次描述每组数据,对于每组数据:

  • 第1 行两个用空格隔开的正整数nm。nm 分别表示选手的数量、导师的数量。
  • 第2 行m 个用空格隔开的正整数:其中第i 个整数为 。 表示编号为i 的导师战队人数的上限。
  • 第3 行至第n + 2 行,每行m 个用空格隔开的非负整数:其中第i + 2 行左起第 j 个数为  。 表示编号为i 的选手将编号为j 的导师编排在了第 志愿。特别地,如果  = 0,则表示该选手没有将该导师填入志愿表。在这一部分,保证每行中不存在某一个正数出现超过 C 次(0 可能出现超 过C 次),同时保证所有  <= m。
  • 第n + 3 行n 个用空格隔开的正整数,其中第i 个整数为 。 表示编号为i 的选手的理想值。在这一部分,保证  <= m。

输出格式:

输出到文件mentor.out 中。

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

  • 第1 行输出n 个用空格隔开的正整数,其中第i 个整数的意义为:在最优的录取方案中,编号为i 的选手会被该档志愿录取。特别地,如果该选手出局,则这个数为m + 1。
  • 第 2 行输出 n 个用空格隔开的非负整数,其中第 i 个整数的意义为:使编号为i 的选手不沮丧,最少需要让他上升的排名数。特别地,如果该选手一定会沮丧,则这个数为i。

此处的图片


solution

咕了几天之后终于来更新了

出题人:我都把算法写题目上了你们还不会

建图设立源点s和汇点t,

源点s向学生连一条流量为1的边,

学生向他的志愿的导师连流量为1的边,

导师向汇点连流量为x的边。

对于第一问,可以从第一名学员开始枚举他的志愿,

每次从上一优先级开始加边,在上一优先级的残量网络上跑最大流,如果他所有的志愿枚举完后还是没有匹配,那么这名选手将会出局。

可持久化图存图?大雾

考虑到n,m很小,暴力存下每个优先级跑完的图。

第二问很显然可以二分他前进的排名,所以第一问记录的图可以用在第二问进行匹配,显然不用像第一问那样依次加志愿,可以把他想要的志愿都加上再跑最大流就行了。

贼有用的存图方法

真不知道我当时为什么只打了一个贼难写的暴力

code:

 

分类: 图论题解

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
DefFrancis Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
DefFrancis
游客
DefFrancis

Luogu貌似没法直接引用图片