[CF1139 E] Maximize Mex 解题报告 (二分图匹配)

interlinkage:

https://codeforces.com/contest/1139/problem/E

description:

有$n$个学生，$m$个社团，每个学生有一个能力值，属于一个社团，在接下来的$d$天里，每天会有一个人退出所在的社团。

每天从每个社团中选出最多一个人组成能力值集合${p_i}$使得其$mex$最大。求出每天的最大$mex$值

solution:

• $mex$经常与二分图模型相关;
• 若答案为$t$，每一个小于$t$的能力值都对应一个提供它的社团。由此构造二分图，左侧是能力值，右侧是社团。若社团$c_i$存在一个学生能力值为$p_i$，那么$p_i$向$c_i$连边;
• 这样跑匈牙利就是了;
• 但是注意到学生是在动态变化的，随着天数的变化学生不断减少，我们要对二分图实行删边操作。但是匈牙利算法是不支持删边的;
• 于是我们从最后一天开始倒着来，每天加边，这样的话答案就是非严格单调增的;
• 加边不会影响之前的匹配，倒序输出即可;

code:

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<queue>

#include<cmath>

using namespace std;

const int N=1e4+;

int n,m,tot;

int head[N<<],a[N],b[N],c[N],used[N],match[N],ans[N];

struct EDGE

{

    int to,nxt;

}edge[N<<];

void add(int u,int v)

{

    edge[++tot]=(EDGE){v,head[u]};

    head[u]=tot;

}

inline int read()

{

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int find(int x)

{

    if (used[x]) return ;

    used[x]=;

    for (int i=head[x];i;i=edge[i].nxt)

    if (match[edge[i].to]==-||find(match[edge[i].to]))

    {

        match[edge[i].to]=x;

        return ;

    }

    return ;

}

int main()

{

    memset(match,-,sizeof(match));

    n=read();m=read();

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<=n;i++) b[i]=read();

    int q=read();

    for (int i=;i<=q;i++) c[i]=read(),used[c[i]]=;

    for (int i=;i<=n;i++) if (!used[i]) add(a[i],b[i]);

    int t=;

    for (int i=q;i>=;i--)

    {

        memset(used,,sizeof(used));

        while (find(t))

        {

            ++t;

            memset(used,,sizeof(used));

        }

        ans[i]=t;

        add(a[c[i]],b[c[i]]);

    }

    for (int i=;i<=q;i++) printf("%d\n",ans[i]);

    return ;

}