BZOJ5251【2018多省省队联测】劈配 <网络流>

Posted on Symbols count in article: 2.3k Reading time ≈ 8 mins.

Problem

【2018多省省队联测】劈配

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

一年一度的综艺节目《中国新代码》又开始了。Zayid\mathrm{Zayid}从小就梦想成为一名程序员，他觉得这是一个展示自己的舞台，于是他毫不犹豫地报名了。
轻车熟路的Zayid\mathrm{Zayid}顺利地通过了海选，接下来的环节是导师盲选，这一阶段的规则是这样的：
总共nn名参赛选手（编号从11至nn）每人写出一份代码并介绍自己的梦想。接着由所有导师对这些选手进行排名。
为了避免后续的麻烦，规定不存在排名并列的情况。
同时，每名选手都将独立地填写一份志愿表，来对总共mm位导师（编号从11至mm）作出评价。志愿表上包含了共mm档志愿。对于每一档志愿，选手被允许填写最多CC位导师，每位导师最多被每位选手填写一次（放弃某些导师也是被允许的）。
在双方的工作都完成后，进行录取工作。每位导师都有自己战队的人数上限，这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。
节目组对“前ii名的录取结果最优”作出如下定义：

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

如果一种方案满足“前nn名的录取结果最优”，那么我们可以简称这种方案是最优的。
举例而言，22位导师TT老师、FF老师的战队人数上限分别都是11人；22位选手Zayid\mathrm{Zayid}、DuckD\mathrm{DuckD}分列第1、21、2名。那么下面33种志愿表及其对应的最优录取结果如表中所示：

![][1]

可以证明，对于上面的志愿表，对应的方案都是唯一的最优录取结果。
每个人都有一个自己的理想值sis_i，表示第ii位同学希望自己被第sis_i或更高的志愿录取，如果没有，那么他就会非常沮丧。
现在，所有选手的志愿表和排名都已公示。巧合的是，每位选手的排名都恰好与它们的编号相同。
对于每一位选手，Zayid\mathrm{Zayid}都想知道下面两个问题的答案：

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

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

Input

每个测试点包含多组测试数据，第一行22个用空格隔开的非负整数T,CT,C，分别表示数据组数、每档志愿最多允许填写的导师数目。
接下来依次描述每组数据，对于每组数据：

  • 第11行两个用空格隔开的正整数n,mn,m。n,mn,m分别表示选手的数量、导师的数量。
  • 第22行mm个用空格隔开的正整数：其中第ii个整数为bib_i。BiB_i表示编号为ii的导师战队人数的上限。
  • 第33行至第n+2n+2行，每行mm个用空格隔开的非负整数：其中第i+2i+2行左起第jj个数为ai,ja_{i,j}
    • ai,ja_{i,j}表示编号为ii的选手将编号为jj的导师编排在了第ai,ja_{i,j}志愿。特别地，如果ai,j=0a_{i,j}=0，则表示该选手没有将该导师填入志愿表。
    • 在这一部分，保证每行中不存在某一个正数出现超过CC次（00可能出现超过CC次），同时保证所有ai,j≤ma_{i,j}\le m。
  • 第n+3n+3行nn个用空格隔开的正整数，其中第ii个整数为SiS_i
    • SiS_i表示编号为ii的选手的理想值。
    • 在这一部分，保证Si≤mS_i\le m。

Output

按顺序输出每组数据的答案。对于每组数据，输出22行：

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3 5
2 2
1 1
2 2
1 2
1 1
2 2
1 1
1 2
1 2
2 1
2 2
1 1
0 1
0 1
2 2

Sample Output

1
2
3
4
5
6
2 1
1 0
1 2
0 1
1 3
0 1

HINT

样例解释
三组数据分别与题目描述中的三个表格对应。
对于第11组数据：由于选手11没有填写第一志愿，所以他一定无法被第一志愿录取，也就一定会沮丧。选手22按原排名就不沮丧，因此他不需要提升排名。
对于第22组和第33组数据：11号选手都不需要提升排名。而希望被第一志愿录取的22号选手都必须升到第11名才能如愿。
数据范围
T≤5,  m≤n≤200,  Bi≤NT\le 5,\;m\le n\le 200,\;B_i\le N
原题面

标签：网络流

Solution

九省联考Day2\mathrm{Day2}唯一一道有区分度的题。

容易看出本质就是一个二分图匹配。只不过每条边的优先度是有差别的。
第一问
先将源点到每个学员流量为11的边和导师到汇点的流量为bb的边连上。
顺次考虑每个学员，每次将一个志愿中的所有导师的边加到图里，看能否使其找到匹配，找到就退出，标记此志愿为答案。

第二问
考虑像第一问那样判断，那么就可以每次加入一个学员，判断能否达到要求，当加入一个学员后不能达到要求时，此时加入的学员数−1此时加入的学员数-1为此人满足要求的最大名次，用其真实名次减去即可得到答案。注意特判无论如何都不能满足的情况。
另外，这里还可以二分答案，不过直接暴力加入在BZOJ\mathrm{BZOJ}上已经可以过了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define MAX_N 500
#define MAX_M 100000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, rk[MAX_N+5], mi[MAX_N+5];
int b[MAX_N+5], d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5]; vector <int> a[205][205];
void init() {s = 0, t = n+m+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0; cpy(); while (BFS()) ret += DFS(s, INF), rec(); return ret;}
void build() {
    init();
    for (int i = 1; i <= n; i++) addedge(s, i, 1);
    for (int i = 1; i <= m; i++) addedge(i+n, t, b[i]);
}
bool inc(int p, int l, int r) {
    for (int i = l; i <= r; i++)
        for (int j = 0; j < (int)a[p][i].size(); j++)
            addedge(p, a[p][i][j]+n, 1);
    return Dinic();
}
int main() {
    int T, C; read(T), read(C);
    while (T--) {
        read(n), read(m);
        for (int i = 1; i <= m; i++) read(b[i]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                a[i][j].clear();
        for (int i = 1; i <= n; i++)
            for (int j = 1, x; j <= m; j++)
                read(x), a[i][x].push_back(j);
        build();
        for (int i = 1; i <= n; i++)
            for (rk[i] = 1; rk[i] <= m; rk[i]++)
                if (inc(i, rk[i], rk[i])) break;
        for (int i = 1, k; i <= n; i++) {
            read(k), mi[i] = i, build();
            if (!inc(i, 1, k)) continue;
            for (int j = 1; mi[i]--; j++) if (rk[j] <= m)
                if (!inc(j, rk[j], rk[j])) break;
        }
        for (int i = 1; i <= n; i++) printf("%d ", rk[i]);	puts("");
        for (int i = 1; i <= n; i++) printf("%d ", mi[i]);	puts("");
    }
    return 0;
}