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

作者: wjyyy 分类: 二分,网络流,解题报告,贪心 发布时间: 2019-03-26 19:45

点击量:64

一道灵活的网络流题目。

题目背景

一年一度的综艺节目《中国新代码》又开始了。 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;
}

说点什么

avatar
  Subscribe  
提醒
/* */