本文共 3436 字，大约阅读时间需要 11 分钟。

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 32 11 34 62 52 45 45 63 651 2 3 3 1 21 2 3 4 5 64 5 6 6 4 52 3 4 2 3 42 2 2 2 2 2

Sample Output:YesError: Too many species.YesNoError: Too few species.

七月唯二能送分的题目，判断每块地的邻接土地上动物是否相等，还有set去重

//k种动物分到N块地上，不要有两种相同的生物是邻居 //记录的是哪两块地是连着的，判断两块相邻的地不要有相同的动物//动物种类要等于k，如果不等于k就输出大于小于//如果等于k但是相邻地有相同动物就no#include
   
    #include
    
     #include
     
      using namespace std;const int maxn = 505;const int INF = 1000000000;vector
      
        Adj[maxn]; int main(){
   	int n,r,k;	cin>>n>>r>>k;	int u,v;	for(int i = 0; i < r; i++){
   		cin>>u>>v;		Adj[u].push_back(v);		Adj[v].push_back(u);	}	int q;	cin>>q;	for(int i = 0; i < q; i++){
   		vector
       
         v(n+2);		set
        
          s; for(int j = 1; j <= n; j++){ cin>>v[j]; s.insert(v[j]); } if(s.size() > k){ cout<<"Error: Too many species.\n"; continue; } if(s.size() < k){ cout<<"Error: Too few species.\n"; continue; } //然后遍历每块地的所有连通土地，看看这块地和它的连通土地的动物是否相同 bool flag = true; for(int i = 1; i <= n; i++){ for(int j = 0; j < Adj[i].size(); j++){ if(v[i] == v[Adj[i][j]]){ flag = false; break; } } if(!flag) break; } if(!flag) cout<<"No\n"; else cout<<"Yes\n"; } return 0;}
        
       
      
     
    
   

//邻接表存图，判断每个顶点的所有邻接顶点的动物是否和当前顶点的一样，如果一样，就false//如果一样，记得用set判断动物种类的多少#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 505;vector
       
         Adj[maxn];int main(){
   	int n,m,k;//n块地，m中关系，k种动物,地和动物都是从1开始标号的 	cin>>n>>m>>k;	int u,v;	for(int i = 0; i < m; i++){
   		cin>>u>>v;		Adj[u].push_back(v);		Adj[v].push_back(u);	} 	int q;	cin>>q;	for(int i = 0; i < q; i++){
   		vector
        
          v(n+2);//记录每块地上的动物 set
         
           s; bool flag = true; for(int j = 1; j <= n; j++){ cin>>v[j]; s.insert(v[j]); } for(int j = 1; j <= n; j++){ for(int l = 0; l < Adj[j].size(); l++){ if(v[j] == v[Adj[j][l]]) flag = false; } } if(s.size() == k){ if(flag) cout<<"yes\n"; else cout<<"no\n"; } else{ if(s.size() < k) cout<<"few\n"; else cout<<"more\n"; } } return 0;}
         
        
       
      
     
    
   

转载地址：http://qkjuk.baihongyu.com/