1170 Safari Park (25)

A safari park（野生动物园）has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the two neighboring regions. Of course, they also realize that this is an NP complete problem, you are not expected to solve it. Instead, they have designed several distribution plans. Your job is to write a program to help them tell if a plan is feasible.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 integers: N (0<N≤500), the number of regions; R (≥0), the number of neighboring relations, and K (0<K≤N), the number of species of animals. The regions and the species are both indexed from 1 to N.

Then R lines follow, each gives the indices of a pair of neighboring regions, separated by a space.

Finally there is a positive M (≤20) followed by M lines of distribution plans. Each plan gives N indices of species in a line (the i-th index is the animal in the i-th rigion), separated by spaces. It is guaranteed that any pair of neighboring regions must be different, and there is no duplicated neighboring relations.

Output Specification:

For each plan, print in a line Yes if no animals in the two neighboring regions are the same, or No otherwise. However, if the number of species given in a plan is not K, you must print Error: Too many species. or Error: Too few species. according to the case.

Sample Input:

6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
5
1 2 3 3 1 2
1 2 3 4 5 6
4 5 6 6 4 5
2 3 4 2 3 4
2 2 2 2 2 2

Sample Output:

Yes
Error: Too many species.
Yes
No
Error: Too few species.

题目大意：野生动物园有K种动物，N个区域。管理人员希望将动物安排到所有区域，但相邻区域不能是同一种动物。当然，这是一个NP完全问题，不用去解决它。判断工作人员给出的方案是否可行。

分析：可以抽象为N个节点，R条边，边的两个端点的颜色不能相同。对于给出的方案，要判断：1、边的两个端点颜色是否相同，即值是否相同。2、出现的所有颜色是否恰好等于k。按照2个条件检查即可。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint n,r,k,m;scanf("%d%d%d",&n,&r,&k);int edge[n+5][n+5];for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)edge[i][j]=0;for(int i=0;i<r;++i){int a,b;scanf("%d%d",&a,&b);edge[a][b]=edge[b][a]=1;}scanf("%d",&m);while(m--){int cnt=0,f=1;int ques[n+5]={0},flag[100000]={0};for(int i=1;i<=n;++i){scanf("%d",&ques[i]);if(flag[ques[i]]==0)flag[ques[i]]=1,cnt++;if(i>1&&f){for(int j=1;j<i;++j){if(edge[i][j]&&ques[i]==ques[j]){f=0;break;}}}}if(cnt>k)printf("Error: Too many species.\n");else if(cnt<k)printf("Error: Too few species.\n");else{if(f)printf("Yes\n");else printf("No\n");}}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}