CF1139E Maximize Mex解题报告

解题报告

CF1139E Maximize Mex解题报告：

更好的阅读体验

题意

• $n$名学生，$m$个社团，每个学生$i$属于社团$c_i$，能力值为$p_i$；
• 学校有一个为期为$d$天的活动，第$i$天，学生$k_i$会推出社团；
• 定义一个队伍的能力值为所有学生的能力值的$mex$，即所有学生能力值组成的集合中没有出现的最小非负整数；
• 每一天学校都要从各社团选出一个人组成队伍使队伍的能力值最大，求每一天的能力值。
• 数据范围：$1\leqslant n,m\leqslant 5\cdot 10^3,0\leqslant p_i\leqslant 5\cdot 10^3$。

分析

考虑将每个社团抽象为一个点，每个能力值抽象为一个点，社团与所有它成员的能力值连边，那么我们可以用匈牙利算法来解决这个$mex$：每一次多取一个能力值，如果可以那么$mex$加一，否则当前$mex$就是最终答案。

可以不断删边（标记每一条边删掉就好了），然后用匈牙利做到$O((maxp\cdot n+m)\cdot d)$，但是仍然无法通过。

考虑将删边转化为加边（时间倒流），然后不难发现$mex$是递增的。

因为$mex$是递增的，所以每一次匈牙利都可以从上一次结束的位置开始，这样我们的复杂度就优化成了$O(maxp\cdot d+maxp\cdot n)$。

代码

#include<stdio.h>
#include<string.h>
const int maxn=5005,maxm=5005,maxd=5005;
int n,m,d,e,stp,ans;
int start[maxn],to[maxm],then[maxm],c[maxn],p[maxn],k[maxd],vis[maxn],match[maxn],flg[maxn],res[maxd];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
int dfs(int x){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y]==stp)
            continue;
        vis[y]=stp;
        if(match[y]==-1||dfs(match[y])){
            match[y]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    memset(match,-1,sizeof(match));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    scanf("%d",&d);
    for(int i=1;i<=d;i++){
        scanf("%d",&k[i]);
        flg[k[i]]=1;
    }
    for(int i=1;i<=n;i++)
        if(flg[i]==0)
            add(p[i],c[i]);
    for(int i=d;i>=1;i--){
        for(int j=ans;;j++){
            stp++;
            if(dfs(j)==0){
                ans=j;
                break;
            }
        }
        res[i]=ans;
        add(p[k[i]],c[k[i]]);
    } 
    for(int i=1;i<=d;i++)
        printf("%d\n",res[i]);
    return 0;
}