题解 CF1139E 【Maximize Mex】
wjyyy
2019-03-27 21:54:56
## 前言
我发现我有道叫[[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;
}
```