洛谷 P4382 / loj 2477 [九省联考2018] 劈配 题解【网络流】【贪心】【二分答案】

点击量：571

一道灵活的网络流题目。

目录

题目背景

一年一度的综艺节目《中国新代码》又开始了。 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$ 种志愿表及其对应的最优录取结果如表中所示：

选手	第 $1$ 志愿	第 $2$ 志愿	录取志愿	加入战队
Zayid	N/A	T 老师、F 老师	$2$	F 老师
DuckD	T 老师	F 老师	$1$	T 老师

选手	第 $1$ 志愿	第 $2$ 志愿	录取志愿	加入战队
Zayid	T 老师	F 老师	$1$	T 老师
DuckD	T 老师	F 老师	$2$	F 老师

选手	第 $1$ 志愿	第 $2$ 志愿	录取志愿	加入战队
Zayid	F 老师	N/A	$1$	F 老师
DuckD	F 老师	N/A	出局	N/A

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

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

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

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

• 在最优的录取方案中，他会被第几志愿录取。
• 在其他选手相对排名不变的情况下，至少上升多少名才能使得他不沮丧。
  作为《中国新代码》的实力派代码手，Zayid 当然轻松地解决了这个问题。不过他还是想请你再算一遍，来检验自己计算的正确性。

输入格式

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

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

接下来依次描述每组数据，对于每组数据：
– 第 $1$ 行两个用空格隔开的正整数 $n,m$。
– $n,m$ 分别表示选手的数量、导师的数量。
– 第 $2$ 行 $m$ 个用空格隔开的正整数：其中第 $i$ 个整数为 $b_i$。
– $b_i$ 表示编号为 $i$ 的导师战队人数的上限。
– 第 $3$ 行至第 $n+2$ 行，每行 $m$ 个用空格隔开的非负整数：其中第 $i+2$ 行左起第 $j$ 个数为 $a_{i,j}$。
– $a_{i,j}$ 表示编号为 $i$ 的选手将编号为 $j$ 的导师编排在了第 $a_{i,j}$ 志愿。特别地，如果 $a_{i,j}=0$，则表示该选手没有将该导师填入志愿表。
– 在这一部分，保证每行中不存在某一个正数出现超过 $C$ 次（$0$ 可能出现超过 $C$ 次），同时保证所有 $a_{i,j}\le m$。
– 第 $n+3$ 行 $n$ 个用空格隔开的正整数，其中第 $i$ 个整数为 $s_i$。
– $s_i$ 表示编号为 $i$ 的选手的理想值。
– 在这一部分，保证 $s_i\le m$。

输出格式

输出到文件 mentor.out 中。

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

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

样例 1 输入

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

样例 1 输出

2 1
1 0
1 2
0 1
1 3
0 1 

样例 1 解释

三组数据分别与【题目描述】中的三个表格对应。

对于第 $1$ 组数据：由于选手 $1$ 没有填写第一志愿，所以他一定无法被第一志愿录取，也就一定会沮丧。选手 $2$ 按原排名就不沮丧，因此他不需要提升排名。

对于第 $2$ 组和第 $3$ 组数据：$1$ 号选手都不需要提升排名。而希望被第一志愿录取的 $2$ 号选手都必须升到第 $1$ 名才能如愿。

样例 2 输入

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

样例 2 输出

1 1 3 2
0 0 0 0

样例 2 解释

$1$ 号选手的第一志愿只填写了 $2$ 号导师，因此 $1$ 号选手必定被 $2$ 号导师录取。

$2$ 号选手的第一志愿只填写了 $3$ 号导师，因此 $2$ 号选手必定被 $3$ 号导师录取。

由于 $2,3$ 号导师均满员，且 $3,4$ 号选手均填写了 $1$ 号导师，因此它们都会被 $1$ 号导师录取。
所以 $1,2$ 号选手均被第 $1$ 志愿录取，$3$ 号选手被第 $3$ 志愿录取，$4$ 号选手被第 $2​$ 志愿录取。

由于他们都如愿以偿了，所以他们都不需要提升名次。

子任务

测试点编号	$n\le$	$m\le$	$C$	其他约定
$1$	$10$	$1$	$=1$	无
$2$		$2$	$=2$	$s_i=m$
$3$		$3$	$=3$	无
$4$	$100$	$100$	$=1$	$b_i=1$
$5$				无
$6$	$200$	$200$		$b_i=1$
$7$				无
$8$	$100$	$100$	$=10$
$9$	$100$	$100$		$b_i=1$
$10$				无

对于所有测试点，保证 $T\le 5$。

对于所有测试点中的所有数据，保证 $m\le n\le 200,b_i\le n$。

题解

题目特别长，但是题意也比较好理解。

就是尽可能满足较高的志愿，且志愿中任意满足一个即可。同时每个导师可以选择多个选手，选择也是有限的。

题目名称题目描述已经很明显了，它是一个二分图，因此进行一个匹配。但是导师可以选择多个选手，所以使用 Dinic 而不是匈牙利。实际上由于 $C\le 10$，匈牙利可以拆点跑。

然而每次最多增加一条增广路，Dinic 也只用进行 bfs。

接下来顺着排名匹配每一个选手的志愿，志愿从小到大枚举。如果当前选手该志愿选的导师都没有匹配成功，我们可以直接把这些边删掉，这样最终保留下来的边数可以维持在 $O(nC)$。如果匹配成功了，则把这个志愿的所有边都保留下来，并把这个选手第一问的答案置为志愿编号。

下面认为二分图匹配的复杂度为 $O(VE)=O(n^2C)$。

第二问其实也是动态的，如果枚举要上升多少名，每次对每个点重新做一遍上面的工作，那样时间复杂度是 $O(Tn^4C)​$ 的。

分析得，如果上升 $k$ 名可以使这个选手不沮丧，那么上升 $j\in [k,i]$ 名都不会使他沮丧。那么这一步可以二分，得到 $O(Tn^3C\log n)$ 的复杂度。但是还是无法通过。

我们知道，匹配的过程是不会影响到前面的选手的志愿编号的。也就是说，即使修改了前面人的战队，也不会修改他的志愿编号，因为选手代表的点的出边一定属于同一志愿，反向增广后不会影响第一问的答案。匹配到前 $i$ 个人的第一问就是一个阶段。

这样我们可以把已经匹配了 $i,\ i\in[0,n-1]$ 个人的图分别存下来，一共有 $n$ 张图。

我们每次对于一个选手 $i$ 计算他需要上升多少名，仍然使用二分。假设现在二分到他需要上升 $mid$ 名，则先把 $i$ 和 $i-mid$ 的信息交换一下，然后取出 $i-mid-1$ 的图，判断 $i-mid$ 能填到的最优志愿。

如果这个最优志愿 $\le s_i​$，那么说明此时已经满足条件了；否则不满足条件。最终二分到一个最小的 $mid​$ 满足 $i-mid​$ 能填到的最优志愿 $\le s_i​$ 的排名，作为第二问的答案。

本题多组数据，注意清空 vector。此外，当匹配不到答案的时候，第一问要设为 $m+1$（也是题目的要求），否则会对第二问造成影响。

时间复杂度 $O(T(n^2m+n^2C\log n))$。

Code：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using std::vector;
using std::swap;
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[5000],E[205][5000];
int head[500],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0);
    head[to]=ecnt;
}
int Head[205][500],Ecnt[205];
int q[500],pre[500];
bool bfs()
{
    int l=0,r=0;
    memset(pre,-1,sizeof(pre));
    q[++r]=0;
    pre[0]=1;
    while(l<r)
    {
        int x=q[++l];
        if(x==432)
            break;
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i].v&&pre[e[i].n]==-1)
            {
                pre[e[i].n]=i;
                q[++r]=e[i].n;
            }
    }
    pre[0]=-1;
    if(~pre[432])
    {
        int p=pre[432];
        while(~p)
        {
            --e[p].v;
            ++e[p^1].v;
            p=pre[e[p^1].n];
        }
        return true;
    }
    return false;
}
vector<int> v[205][205];
int n,m;
int b[205],s[205],ans[205];
void solve()
{
    memset(head,-1,sizeof(head));
    ecnt=-1;
    for(int i=1;i<=n;++i)
        add(0,i,1);
    for(int i=1;i<=m;++i)
        add(n+i,432,b[i]);
    Ecnt[0]=ecnt;
    for(int i=0;i<=432;++i)
        Head[0][i]=head[i];
    for(int i=0;i<=ecnt;++i)
        E[0][i]=e[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            for(vector<int>::iterator it=v[i][j].begin();it!=v[i][j].end();++it)
                add(i,n+*it,1);
            if(bfs())
            {
                ans[i]=j;
                break;
            }
            for(vector<int>::iterator it=v[i][j].begin();it!=v[i][j].end();++it)
            {
                ecnt-=2;
                head[i]=e[head[i]].nxt;
                head[n+*it]=e[head[n+*it]].nxt;
            }
            if(j==m)
                ans[i]=m+1;
        }
        Ecnt[i]=ecnt;
        for(int j=0;j<=432;++j)
            Head[i][j]=head[j];
        for(int j=0;j<=ecnt;++j)
            E[i][j]=e[j];
    }
}
void solve1(int x)//恢复 x 之前的图 并增广 x+1
{
    ecnt=Ecnt[x];
    for(int i=0;i<=432;++i)
        head[i]=Head[x][i];
    for(int i=0;i<=ecnt;++i)
        e[i]=E[x][i];
    ++x;
    for(int i=1;i<=m;++i)
    {
        for(vector<int>::iterator it=v[x][i].begin();it!=v[x][i].end();++it)
            add(x,n+*it,1);
        if(bfs())
        {
            ans[x]=i;
            break;
        }
        for(vector<int>::iterator it=v[x][i].begin();it!=v[x][i].end();++it)
        {
            ecnt-=2;
            head[x]=e[head[x]].nxt;
            head[n+*it]=e[head[n+*it]].nxt;
        }
        if(i==m)
            ans[x]=m+1;
    }
}
int main()
{
    int T=read(),u;
    int C=read();
    while(T--)
    {
        n=read();
        m=read();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                v[i][j].clear();
        for(int i=1;i<=m;++i)
            b[i]=read();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                u=read();
                if(u)
                    v[i][u].push_back(j);
            }
        for(int i=1;i<=n;++i)
            s[i]=read();
        solve();
        for(int i=1;i<=n;++i)
            printf("%d ",ans[i]);
        puts("");
        for(int i=1;i<=n;++i)
        {
            int l=0,r=i,mid;
            while(l<r)
            {
                mid=(l+r)>>1;
                swap(v[i],v[i-mid]);
                solve1(i-mid-1);
                if(ans[i-mid]<=s[i])
                    r=mid;
                else
                    l=mid+1;
                swap(v[i],v[i-mid]);
            }
            printf("%d ",l);
        }
        puts("");
    }
    return 0;
}