Posted on 2011-11-06 16:40
C小加 閱讀(1452)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
題意：你準備邀請你的朋友來參加你的party，你想把所有的朋友都邀請過來，但是有的朋友邀請過來后效果不是很好，你就想出了一些條件，參加party的朋友必須滿足：所有來參加party的朋友中，每個朋友最少和A個人是朋友，最少和B個人是陌生人，當(dāng)然這些人中不包括你。你要求出最多能有多少個人來參加你的party。
思路：隊里周賽的一道題，也是我唯一AC的題。初看題感覺不難，想到了一種方法但沒有立馬去寫，怕會超時。然后成哥告訴我數(shù)據(jù)最多只有100個點，我一看果然如此，就很果斷的水掉了。思路很簡單，每次找到不合法的朋友，找到之后消除他在關(guān)系群里的所有關(guān)系，然后重新找，直至每一個人都是合法的。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN=103;
int n,m,a,b,cnt;
int map[MAXN][MAXN],flag[MAXN];
typedef struct
{
int f,unf;
}People;
People p[MAXN];
void Init()
{
memset(p,0,sizeof(p));
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
}
void Read()
{
cnt=n;
int p1,p2;
for(int i=0;i<m;i++)
{
scanf("%d %d",&p1,&p2);
map[p1][p2]=map[p2][p1]=1;
p[p1].f++;
p[p2].f++;
}
for(int i=0;i<n;i++)
{
p[i].unf=n-p[i].f-1;
}
}
void Solve()
{
while(1)
{
int i=0;
for(;i<n;i++)
{
if(flag[i]) continue;
if(p[i].f<a||p[i].unf<b)
{
flag[i]=1;
for(int j=0;j<n;j++)
{
if(map[i][j])
{
p[j].f--;
map[i][j]=map[j][i]=0;
}
else p[j].unf--;
}
cnt--;
break;
}
}
if(i==n) break;
}
}
void Print()
{
static int c=1;
printf("Case #%d: %d\n",c++,cnt);
}
int main()
{
while(scanf("%d %d %d %d",&n,&m,&a,&b)&&(n||m||a||b))
{
Init();
Read();
Solve();
Print();
}
return 0;
}