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