2021年初寒假训练第24场 B. 庆功会（搜索）

2021年初寒假训练第24场 B. 庆功会（搜索）

Description

NOIP结束之后，为了庆祝同学们取得的优异成绩，学校决定召开一次 Party。发邀请函的工作交到了你的手上。 为了能让这次Party开得圆满顺利，对于这次邀请的同学们有两个要求：首先，每个同学认识的同学不少于a个，否则的话这个同学会感到孤单；其次，每个同学不认识的同学不少于b个，否则的话他（她）就没有机会认识新朋友。 但是学校想让这次Party开得越大越好。所以请你计算一下，最多可以邀请多少个同学？

Input

第一行四个数，N,M,a,b。总共有 N 个同学，这些同学从 1 到 N编号。 后接 MM行，每行两个数 ai、bi，表示这两个同学互相认识。

Output

一行一个数，表示最多可以邀请的同学数。

Samples

Input

4 3 1 11 22 33 4

Output

4

Input

5 5 2 1 2 3 3 1 4 5 3 4 2 5

Output

4

Hint

【数据规模】 对于20%的数据，N<20。 对于全部的数据，1≤a,b≤N≤500，0≤M≤N∗(N–1)/2。

思路：

正着考虑不好处理，考虑反着考虑。

假设开始的时候所有人都被选上，那么有哪些人是不应当选的呢。

就是认识的人小于a或是不认识的人小于b的人。

把这些人去除后，会对剩下的人产生影响。

dfs处理就好了。

OJ有点卡快读。

代码：

const int maxn=510;int mp[maxn][maxn];int da[maxn],db[maxn];int n,m,a,b;bool vis[maxn];void dfs(int u){ for(int i=1;i<=n;i++) if(!vis[i]){//优化 if(mp[u][i]) da[i]--;///认识的话，认识的人-1 else db[i]--;//否则，不认识的人-1 if(da[i]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。