关于算法-数据结构:PAT甲级2020年春季考试-73-Safari-Park

7-3 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 个区域(K<N)，每一个区域都有一种动物(可反复)，先给出每个区域相邻的关系和 M 个调配打算，每一个调配打算给出，每一个区域调配那个品种的动物，请问该计划分配的动物品种数目是否为 K，如果多于 K，输入Error: Too many species.，如果小于 K，输入Error: Too few species.。如果等于 K，那么判断是否存在两个相邻的区域有着雷同品种的动物，如果没有，就输入 Yes, 否则输入 No。

算法思路：

和之前的 vertex coloring 是一种类型的题目，其本质就是查问是否存在某一条边的两个顶点，其调配的动物品种编号雷同 (色彩雷同)。那么咱们应用edges 数组存储所有的边，map speciesPerRegion保留每一个区域所调配的动物品种的映射，set species汇合存储每一个打算所用到的动物品种数目，依据其大小与 K 的关系进行输入，在等于 K 的时候，遍历每一条边，判断两个顶点 a 和 b 是否呈现 speciesPerRegion[a]==speciesPerRegion[b]，如果呈现阐明该打算不符合要求，输入 No, 否则输入 Yes。对于species 大小大于 K 和小于 K 的时候就输入相应信息即可。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<string>
#include<iostream>

using namespace std;

struct Edge{int a,b;};

int N,R,K;// 顶点的个数，边数，动物品种数目
vector<Edge> edges;

int main(){scanf("%d %d %d",&N,&R,&K);
    Edge edge;
    for (int i = 0; i < R; ++i) { 
        int a,b;
        scanf("%d %d",&edge.a,&edge.b);
        edges.push_back(edge);
    }
    int M;
    scanf("%d",&M);
    for (int j = 0; j < M; ++j) {
        unordered_set<int> species;// 品种数目
        unordered_map<int,int> speciesPerRegion;// 每一个 region 的物种数目
        for (int i = 1; i <= N; ++i) {
            int num;
            scanf("%d",&num);
            species.insert(num);
            speciesPerRegion[i] = num;
        }
        if(species.size()>K){printf("Error: Too many species.\n");
        } else if(species.size()<K){printf("Error: Too few species.\n");
        } else {
            // 遍历每一条边
            bool isTrue = true;
            for(auto &item:edges){if(speciesPerRegion[item.a]==speciesPerRegion[item.b]){
                    isTrue = false;
                    break;
                }
            }
            if(isTrue){printf("Yes\n");
            } else {printf("No\n");
            }
        }
    }
    return 0;
}