题目大意
有 n 个学生 m 个社团，每个学生有一个能力值 p_i 属于 c_i 社团，接下来的 d 天里，每天由校长钦点一个学生滚蛋，然后由你从每个社团选一个人（没人就不选），对于每天，求这些人 p_i 的 mex 的最大值
mex 即为序列中最小的非负整数
题解
考虑二分图匹配
左部为学生的能力值，右部为社团。
将学生的能力值与其社团连边。
从最后一天开始匹配，往前的话，由于人只多不少， mex 不会减少（最坏的情况你都可以选择上一次的人员构成）
代码里都加了一，最后答案减了一，这是因为我写的链式前向星和匈牙利不能有0元素（其实稍微改改也行）
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<bits/stdc++.h> using namespace std; const int MAXN=5003*2; int Head[MAXN],to[MAXN<<1],Nt[MAXN<<1],tot; int n,m,d; int p[MAXN],c[MAXN],ans[MAXN]; int del[MAXN]; bool delt[MAXN]; bool vis[MAXN]; int match[MAXN]; void add(int x,int y){ Nt[++tot]=Head[x]; to[tot]=y; Head[x]=tot; } bool dfs(int x){ for(int i=Head[x],y;i;i=Nt[i]){ if(vis[y=to[i]])continue;vis[y]=1; if(!match[y]||dfs(match[y])){ match[y]=x;return true; } } return false; } int main(){ 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>>del[i];delt[del[i]]=1;} for(int i=1;i<=n;i++){ if(delt[i])continue; add(p[i]+1,c[i]+5001); } int t=1; for(int i=d;i>=1;i--){ memset(vis,0,sizeof(vis)); while(dfs(t)){ t++; memset(vis,0,sizeof(vis)); } ans[i]=t; add(p[del[i]]+1,c[del[i]]+5001); } for(int i=1;i<=d;i++)cout<<ans[i]-1<<endl; return 0; } |