CF1139E Maximize Mex（二分图匹配，匈牙利算法）

好题。不过之前做过的[SCOI2010]连续攻击游戏跟这题一个套路，我怎么没想到……

题目大意：在一个学校有 $n$ 个学生和 $m$ 个社团，每个学生有一个非负整数能力值 $p_i$，一开始在社团 $c_i$。接下来有 $d$ 天，第 $i$ 天编号为 $k_i$ 的同学会离开他的社团。每天同学离开后会有一场比赛，要从每个社团里选一个人出来组队（如果社团没人了就不管）。队伍的能力是所有队员能力值集合的 $mex$（没出现过的最小非负整数）。问这个 $mex$ 最大是多少。

所有输入的数不超过 $5000$。

直接删除肯定不好搞，可以把删人的操作倒过来，变成加人。

然后我就一直在想数据结构，结果才发现数据结构学傻了……

我们建立一个二分图，一边是能力值，一边是社团。因为一个社团只能选一次，一个能力值最好也只选一次（一个能力值选多次肯定不会更优）。那么直接跑匈牙利，因为答案不降，所以每次试图往更大的扩展，如果能匹配到就继续，匹配不到那么这个值就是最大的 $mex$。接下来一个同学回来，就一条连边。

时间复杂度 $O(n+m(d+\max(p_i)))$。

注意细节，其中有个细节是with初始为 $-1$。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

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

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,m,p[maxn],c[maxn],d,k[maxn],with[maxn],el,head[maxn],to[maxn],nxt[maxn],tmp,ans[maxn];

bool vis[maxn],del[maxn];

inline void add(int u,int v){

    to[++el]=v;nxt[el]=head[u];head[u]=el;

}

bool dfs(int u){

    if(vis[u]) return false;

    vis[u]=true;

    for(int i=head[u];i;i=nxt[i]){

        int v=to[i];

        if(with[v]==- || dfs(with[v])){

            with[u]=v;with[v]=u;

            return true;

        }

    }

    return false;

}

int main(){

    MEM(with,-);

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

    FOR(i,,n) p[i]=read();

    FOR(i,,n) c[i]=read();

    d=read();

    FOR(i,,d) del[k[i]=read()]=true;

    FOR(i,,n) if(!del[i] && p[i]<m) add(p[i],c[i]+m),add(c[i]+m,p[i]);

    ROF(i,d,){

        MEM(vis,);

        while(dfs(tmp)) tmp++,MEM(vis,);

        ans[i]=tmp;

        if(p[k[i]]<m) add(p[k[i]],c[k[i]]+m),add(c[k[i]]+m,p[k[i]]);

    }

    FOR(i,,d) printf("%d\n",ans[i]);

}

巴特西

CF1139E Maximize Mex（二分图匹配，匈牙利算法）

最新文章

热门文章