Codeforces Round #548 (Div. 2) E. Maximize Mex 二分图+逆向加边

题意：

有n个学生，m个社团，每个学生只属于一个社团。在接下来的d天内每天会离开一个学生（再也回不来了）。

现要从剩下的每个社团中挑选一个学生组成team，并最大化他们的mex。

题解：

  顺着二分图的学习摸到这里，最开始想的是正向直接加边魔改一下匈牙利，但是会超时(因为每次加新边后得到的都是新图，匈牙利是不支持加边的)。

  考虑一个非常典的做法：删边==逆向加边。

  有什么好处捏？枚举的时候可以利用之前的信息，从原有的答案往上增加(显然mex是人加的越多，mex越大的)。

  注意建图：注意到其实重要的只是学生的能力值p，所以建边是  p[i] ---> c[i]

细节：在dfs函数中x==0也是一个点，所以初始化是-1；

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int vis[maxn],match[maxn],p[maxn],c[maxn],k[maxn],mp[maxn],out[maxn];
int n,m,d;
vector<int>g[maxn];
int dfs(int x)
{
    for(int i=0;i<g[x].size();i++)
    {   int to=g[x][i];
        if(vis[to]) continue;
        vis[to]=1;
        if(match[to]==-1||dfs(match[to]))
        {
            match[to]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    memset(match,-1,sizeof(match));
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    cin>>d;
    for(int i=1;i<=d;i++) cin>>k[i],mp[k[i]]=1;
    int ok=0;
    for(int i=1;i<=n;i++){
        if(mp[i]) continue;
        g[p[i]].push_back(c[i]);
        ok++;
    }
    int ans=0;
    for(int i=d;i>=1;i--){
        int tmp=ans;
        for(int j=tmp;j<=5000;j++){
           memset(vis,0,sizeof(vis));
           ans=j;
           if(dfs(j)) {} 
           else break;    
        }
        out[i]=ans;
        g[p[k[i]]].push_back(c[k[i]]);
    }
    for(int i=1;i<=d;i++) cout<<out[i]<<endl;
}