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完全问题，不指望你去解决它。相反，他们设计了几个分配方案。你的工作是写一个程序，帮助他们判断一个计划是否可行。
分析：flag标记当前方案是否可行，邻接矩阵E存储连接的区域。使用map<int,vector<int>> A保存对应种类的动物生活在哪个区域。判断A的大小就可以知道有多少种类的动物，和K做比较就可以知道动物数量有没有太多或者太少。遍历所有同种动物，通过邻接矩阵看它们生存的区域之间有没有相邻的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> #include <map> #include <vector> using namespace std; int N, R, K, M, flag, E[505][505]; int main() { cin >> N >> R >> K; for (int i = 1, u, v; i <= R; i++) { cin >> u >> v; E[u][v] = E[v][u] = 1; } for (cin >> M; M; M--) { map<int, vector<int>> A; for (int i = 1, a; i <= N; i++) { cin >> a; A[a].push_back(i); } if(A.size() > K) cout << "Error: Too many species.\n"; else if (A.size() < K) cout << "Error: Too few species.\n"; else { flag = 1; for (auto it : A) { for (int i = 0; i < it.second.size(); i++) { for (int j = i + 1; j < it.second.size(); j++) { if(E[it.second[i]][it.second[j]]) { flag = 0; break; } } } } if (flag) cout << "Yes\n"; else cout << "No\n"; } } return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
