2014
01-26

# Get-Together at Stockholm

Peter has recently decided to hold a party at Stockholm, where the ACM/ICPC 2009 World Final will be held. Unfortunately, despite Peter’s affluence, he is not able to invite all of his friends due to the astronomical price of the air ticket to Stockholm.
He has devised the following rule to determine which subset of his friends will be invited:
a) Any invited person must have at least A acquaintances at the party. This is to ensure everyone at the party will not feel alien.
b) Any invited person must be unfamiliar with at least B people. Otherwise some people may not have the chance to communicate with a stranger.
Given the relationships between Peter’s friends, you are to figure out whom Peter should invite to the party so as to maximize its size.

There are multiple test cases in the input file.
Each test case starts with four integers, N, M, A, and B ( 1 ≤ N ≤ 100 , 0 ≤ M ≤ N*(n-1)/2 , 0 ≤ A , B ≤ N – 1). Each of the following M lines contains
two integers, X and Y, ( 0 ≤ X,Y ≤ N-1 , X≠Y), indicating that friend X and friend Y are acquaintances.
Two successive test cases are separated by a blank line. A case with N = 0, M = 0,A = 0 and B = 0 indicates the end of the input file, and should not be processed by your program.

There are multiple test cases in the input file.
Each test case starts with four integers, N, M, A, and B ( 1 ≤ N ≤ 100 , 0 ≤ M ≤ N*(n-1)/2 , 0 ≤ A , B ≤ N – 1). Each of the following M lines contains
two integers, X and Y, ( 0 ≤ X,Y ≤ N-1 , X≠Y), indicating that friend X and friend Y are acquaintances.
Two successive test cases are separated by a blank line. A case with N = 0, M = 0,A = 0 and B = 0 indicates the end of the input file, and should not be processed by your program.

3 2 1 1
0 1
1 2
4 4 2 1
0 1
1 2
2 3
0 3
0 0 0 0

Case #1: 0
Case #2: 4

**================================**

**================================**

#include
#include
#include

using namespace std;

//acq为相互认识的人的关系图认识为1否则为0
//degeree为每个人认识的人的个数，nacq为不认识的人的个数
int acq[105][105] , degree[105] , nacq[105];
int n , m , a , b;
bool invited[105];//表明一个人是否被邀请了

int main()
{
freopen(“D:\\cruanjian\\桌面\\in.txt” , “r” , stdin);
int cas = 1;
while(~scanf(“%d%d%d%d” , &n , &m ,
&a , &b))
{
if(n == 0 && m == 0
&& a == 0 && b == 0) break;
memset(acq , 0
,sizeof(acq));
memset(degree , 0 ,
sizeof(degree));
memset(invited , true ,
sizeof(invited));//初始化每个人都被邀请了

for(int i = 0 ; i < m ;
i++)
{
int u ,
v;
scanf(“%d%d”
, &u , &v);
acq[u][v] =
acq[v][u] = 1;
degree[u]++;
nacq[u] = n – 1 – degree[u];//计算认识的人和不认识的人，自己要出开
degree[v]++;
nacq[v] = n – 1 – degree[v];
}

int res = n;
bool f =
true;//标志是否所有的人都满足情况了
while(true)
{
f =
true;
for(int i = 0
; i < n ; i++)
{
if(invited[i]
&& (degree[i] < a || nacq[i] < b))
{

invited[i]
= false;//i不满足情况不被邀请
res–;

f
= false;
for(int
j = 0 ; j < n ; j++)//修改与i有关的点
{

if(invited[j]
&& acq[i][j])
{

degree[j]–;

nacq[i]
= n – 1 – degree[j];
}

}

}

}
if(f)
break;//所有的点都被检查完毕了
}
printf(“Case #%d: %d\n” , cas++
, res);
}
return 0;
}