Description
NOIP结束之后，为了庆祝同学们取得的优异成绩，学校决定召开一次 Party。发邀请函的工作交到了你的手上。
为了能让这次Party开得圆满顺利，对于这次邀请的同学们有两个要求：首先，每个同学认识的同学不少于a个，否则的话这个同学会感到孤单；其次，每个同学不认识的同学不少于b个，否则的话他（她）就没有机会认识新朋友。
但是学校想让这次Party开得越大越好。所以请你计算一下，最多可以邀请多少个同学？
Input
第一行四个数，N,M,a,b。总共有 N 个同学，这些同学从 1 到 N编号。
后接 MM行，每行两个数 ai、bi，表示这两个同学互相认识。
Output
一行一个数，表示最多可以邀请的同学数。
Samples
Input
4 3 1 1 1 2 2 3 3 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]<a||db[i]<b){ vis[i]=1; dfs(i); } } } void solve(){ scanf("%d%d%d%d",&n,&m,&a,&b); // n=read(),m=read(),a=read(),b=read(); for(int i=1;i<=m;i++){ //int u=read(),v=read(); int u,v; scanf("%d%d",&u,&v); da[u]++;da[v]++; mp[u][v]=mp[v][u]=1;///两人认识 } for(int i=1;i<=n;i++) db[i]=n-da[i]-1; for(int i=1;i<=n;i++){ if(!vis[i]&&(da[i]<a||db[i]<b)){ ///一定不行 vis[i]=1; dfs(i);///该人不来参加对其他人的影响 } } int res=0; for(int i=1;i<=n;i++) if(!vis[i]) res++;///合理 printf("%d\n",res); }
