题解 CF1139E 【Maximize Mex】

2019-03-27 21:54:56


前言

我发现我有道叫[SCOI2010]连续攻击游戏的题白写了..事实上大家写完那道题就可能有这道题的思路了。

博客传送门

题意

有 $n$ 个学生, $m$ 个社团。每个学生属于一个社团。在接下来的 $d$ 天里,每天会有一个人退团。每天从每个社团中最多选出一个人,使得选出的人的能力值集合 $\{p_i\}$ 的 $\mathrm{mex}$ 值最大。求出每天的最大 $\mathrm{mex}$ 值。

题解

可能建立二分图模型是求 $\mathrm{mex}$ 的一个套路/技巧吧。反正是忘了…但是做题的时候也不知道哪些是经典,干脆以后全部好好落实。

因为每个能力值至少被一个社团提供,而一个社团最多提供一个能力值,由此构造二分图。左侧是能力值,右侧是社团。当存在一个学生能力值为 $p_i$ ,社团为 $c_i$ 时,从 $p_i$ 向 $c_i$ 连边。

但是学生是在动态变化的,而且只会减少人,由此每次询问的答案一定非严格递减。

但是二分图最大匹配的匈牙利算法是不支持删边的,而一次匹配(指左边的一个点)的复杂度就是 $O(m)$ ,每次进行复杂度高达 $O(nmd)$ ,显然不是我们想要的。

考虑反过来,从最终状态加学生,每次的答案一定不会减少。那么我们就假设加完前 $i$ 个学生后,此时的 $\mathrm{mex}$ 是 $t$ 。在二分图左侧 Find(t),此时如果替换,只会替换比 $t$ 小的点,不会造成更劣答案;最终会找到一个没有匹配过的社团,令答案 $+1$ 。

重新加边不会影响原来算好的答案。最终反序输出即可。

时间复杂度 $O(nm+qm)$ 。

Code:

写匈牙利一定要在每次 Find() 函数外调用 Find() 时清空 used[] 啊啊啊啊啊啊否则会 FST

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[5050];
int head[5050],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
}
int s[5050];
bool used[5050];
bool Find(int x)
{
    if(used[x])
        return false;
    used[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(s[e[i].n]==-1||Find(s[e[i].n]))
        {
            s[e[i].n]=x;
            return true;
        }
    return false;
}
int a[5050],b[5050],c[5050];
int ans[5050];
int main()
{
    memset(head,-1,sizeof(head));
    memset(s,-1,sizeof(s));
    int n,m,q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
    {
        scanf("%d",&c[i]);
        used[c[i]]=1;
    }
    for(int i=1;i<=n;++i)
        if(!used[i])
            add(a[i],b[i]);
    int t=0;
    for(int i=q;i>=1;--i)
    {
        memset(used,0,sizeof(used));
        while(Find(t))
        {
            ++t;
            memset(used,0,sizeof(used));
        }
        ans[i]=t;
        add(a[c[i]],b[c[i]]);
    }
    for(int i=1;i<=q;++i)
        printf("%d\n",ans[i]);
    return 0;
}