Posted on 2011-11-06 16:40
C小加 阅读(1411)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
题意：你准备邀请你的朋友来参加你的party，你想把所有的朋友都邀请过来，但是有的朋友邀请过来后效果不是很好，你就想出了一些条件，参加party的朋友必须满足：所有来参加party的朋友中，每个朋友最少和A个人是朋友，最少和B个人是陌生人，当然这些人中不包括你。你要求出最多能有多少个人来参加你的party。
思路：队里周赛的一道题，也是我唯一AC的题。初看题感觉不难，想到了一种方法但没有立马去写，怕会超时。然后成哥告诉我数据最多只有100个点，我一看果然如此，就很果断的水掉了。思路很简单，每次找到不合法的朋友，找到之后消除他在关系群里的所有关系，然后重新找，直至每一个人都是合法的。
#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;
}