题解 CF1139E 【Maximize Mex】

whiteqwq · 2020-10-19 18:34:28 · 题解

CF1139E Maximize Mex解题报告：

更好的阅读体验

题意

• 学校有一个为期为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;
}