首页 > ACM题库 > HDU-杭电 > hdu 2470 Get-Together at Stockholm[解题报告]C++
2014
01-26

hdu 2470 Get-Together at Stockholm[解题报告]C++

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

**================================**
题意:
有个人要邀请他的朋友聚会但是被邀请的人
必须满足所有的人有A个认识,有B个不认识
问最多有多少人会被邀请。
分析:
循环每次把不满足情况的删除,修改于这个
点相关联的点的值。直到找不到不满足情况
的时候。
**================================**

#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;
}


解题转自:http://blog.sina.com.cn/s/blog_a3aa8cc401019kgg.html