题解 CF1139E 【Maximize Mex】

wjyyy

2019-03-27 21:54:56

Solution

## 前言 我发现我有道叫[[SCOI2010]连续攻击游戏](https://www.luogu.org/problemnew/show/P1640)的题白写了..事实上大家写完那道题就可能有这道题的思路了。 [**博客传送门**](http://www.wjyyy.top/3419.html) ## 题意 有 $n$ 个学生,$m$ 个社团。每个学生属于一个社团。在接下来的 $d$ 天里,每天会有一个人退团。每天从每个社团中最多选出一个人,使得选出的人的能力值集合 $\{p_i\}$ 的 $\mathrm{mex}$ 值最大。求出每天的最大 $\mathrm{mex}$ 值。 ## 题解 可能建立二分图模型是求 $\mathrm{mex}$ 的一个套路/技巧吧。反正是忘了…但是做题的时候也不知道哪些是经典,干脆以后全部好好落实。 因为每个能力值**至少**被一个社团提供,而一个社团**最多**提供一个能力值,由此构造二分图。左侧是能力值,右侧是社团。当存在一个学生能力值为 $p_i$,社团为 $c_i$ 时,从 $p_i$ 向 $c_i$ 连边。 但是学生是在动态变化的,而且只会减少人,由此每次询问的答案一定非严格递减。 但是二分图最大匹配的匈牙利算法是不支持删边的,而一次匹配(指左边的一个点)的复杂度就是 $O(m)$,每次进行复杂度高达 $O(nmd)$,显然不是我们想要的。 考虑反过来,从最终状态加学生,每次的答案一定不会减少。那么我们就假设加完前 $i$ 个学生后,此时的 $\mathrm{mex}$ 是 $t$。在二分图左侧 `Find(t)`,此时如果替换,只会替换比 $t$ 小的点,不会造成更劣答案;最终会找到一个没有匹配过的社团,令答案 $+1$。 重新加边不会影响原来算好的答案。最终反序输出即可。 时间复杂度 $O(nm+qm)$。 ## Code: 写匈牙利一定要在每次 `Find()` 函数外调用 `Find()` 时清空 `used[]` 啊啊啊啊啊啊~~否则会 FST~~ ```cpp #include<cstdio> #include<cstring> struct edge { int n,nxt; edge(int n,int nxt) { this->n=n; this->nxt=nxt; } edge(){} }e[5050]; int head[5050],ecnt=-1; void add(int from,int to) { e[++ecnt]=edge(to,head[from]); head[from]=ecnt; } int s[5050]; bool used[5050]; bool Find(int x) { if(used[x]) return false; used[x]=1; for(int i=head[x];~i;i=e[i].nxt) if(s[e[i].n]==-1||Find(s[e[i].n])) { s[e[i].n]=x; return true; } return false; } int a[5050],b[5050],c[5050]; int ans[5050]; int main() { memset(head,-1,sizeof(head)); memset(s,-1,sizeof(s)); int n,m,q; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) scanf("%d",&b[i]); scanf("%d",&q); for(int i=1;i<=q;++i) { scanf("%d",&c[i]); used[c[i]]=1; } for(int i=1;i<=n;++i) if(!used[i]) add(a[i],b[i]); int t=0; for(int i=q;i>=1;--i) { memset(used,0,sizeof(used)); while(Find(t)) { ++t; memset(used,0,sizeof(used)); } ans[i]=t; add(a[c[i]],b[c[i]]); } for(int i=1;i<=q;++i) printf("%d\n",ans[i]); return 0; } ```