hdu 2208の検索

2396 ワード

ああ、かわいい子
Time Limit: 10000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 882    Accepted Submission(s): 244
Problem Description
ああ、子供は面倒ですね.ある幼稚園で、先生はゲームの授業を受けなければなりません.N人の子供がゲームをしなければなりません.ゲームをするときはボールを使います.しかし、幼稚園にはM個のボールしかありません.そして、一部の子供は子供と一緒に遊ぶのが好きではありません.他の子供と一緒に遊ぶのが好きです.例えば、愚かな女の子は馬鹿、愚かな根、愚かな卵たちと一緒に遊ぶのが好きです.馬鹿は馬鹿と一緒に遊ぶのが好きではありません.馬鹿は馬鹿と一緒に遊ぶのが好きです.だから先生は彼らをグループに分けるしかなくて、各グループには少なくとも1つの小さいボールが游ぶことができて、その上各グループ内に2人の小さい子供がいないで、互いに好きではありません.今あなたにこのような幼稚園の子供の間の関係の説明をあげて、先生として、このゲームの授業をよく受けることができますか.
 
 
Input
データには複数のcaseがあり、各caseはまず2つの値N(1<=N<=10)とM(1<=M<=10)を入力し、N人の子供(0からN-1の符号)とM個の小さなボールを表す.次にN行あり、i行目にK(0<=K 
 
Output
各caseに対して、もし先生が良い授業を受けることができたら、YESを出力して、さもなくばNO.
 
 
Sample Input
3 2 2 1 2 2 2 0 2 0 1
 
 
Sample Output
YES
 
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<queue>

#include<algorithm>

#include<map>

#include<iomanip>

#define INF 99999999

using namespace std;



const int MAX=10+10;

bool mark[MAX][MAX];

int n,m,k,a,sum;

int father[MAX];



void dfs(int id,int num){

	if(num>m)return;

	if(sum != -1)return;

	if(id == n){sum=num;return;}

	dfs(id+1,num+1);

	for(int i=0;i<id;++i){

		if(father[i] != i)continue;//      

		int temp=1;

		for(int j=i;j<id && temp;++j){

			if(father[j] == i)temp=mark[id][j];//           i(             ) 

		}

		if(temp){father[id]=i;dfs(id+1,num);}//             

	}

	father[id]=id;

}



void Init(int &n){

	memset(mark,false,sizeof mark);

	for(int i=0;i<n;++i)father[i]=i;

}



int main(){

	while(cin>>n>>m){

		Init(n);

		for(int i=0;i<n;++i){

			cin>>k;

			while(k--){

				cin>>a;

				mark[i][a]=true;

			}

		}

		sum=-1;

		dfs(1,1);//                  

		if(sum != -1)cout<<"YES"<<endl;

		else cout<<"NO"<<endl;

	}

	return 0;

}