类似图的顶点覆盖

核心: 判定相邻的动物园是否是不同的动物

英文很难找关键词

满分

/**
题意:动物园划分区域,相同动物不能在相邻的区域

需要判断相邻的区域是否有相同的动物
在判断物种数量是否超过k个

注意:最后一个测试点有1百万的数据
*/
#include <iostream>
#include <cstring>
#include <unordered_set>
#include <vector>
using namespace std;
const int N = 1000100, M = 100010;
int a[N], b[N], vc[M];
int main()
{
    int m, n, k, q;
    cin >> m >> n >> k;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[i] = x, b[i] = y;
    }
    cin >> q;
    while (q--)
    {
        unordered_set<int> se;
        for (int i = 1; i <= m ; i ++)
        {
            cin >> vc[i];
            se.insert(vc[i]);
        }
        if (se.size() > k) printf("Error: Too many species.\n");
        else if (se.size() < k) printf("Error: Too few species.\n");
        else{
            bool flag = true;
            for(int i = 0; i < n; i++)
            {
                int x = a[i], y = b[i];
                if (vc[x] == vc[y]) flag = false;
            }
            if (!flag) printf("No\n");
            else printf("Yes\n");
        }

    }
}

22分, 一个段错误

#include <iostream>
#include <cstring>
#include <unordered_set>
#include <vector>
using namespace std;
const int N = 510;
int a[N], b[N];

int main()
{
    int m, n, k, q;
    cin >> m >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
    }
    cin >> q;
    while (q--)
    {
        unordered_set<int> se;
        vector<int> vc(m + 2);
        for(int i = 1; i <= m; i++)
        {
            cin >> vc[i];
            se.insert(vc[i]);
        }
        if (se.size() > k) puts("Error: Too many species.");
        else if (se.size() < k) puts("Error: Too few species.");
        else 
        {
            bool f = true;
            for(int i = 0; i < n; i++)
            {
                int x = a[i], y = b[i];
                if (vc[x] == vc[y]) {
                    f = false;
                    break;
                }
            }
            if (f) puts("Yes");
            else puts("No");
        }
    }
}

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.

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
OutPut:
Yes
Error: Too many species.
Yes
No
Error: Too few species.

22分, 有一个段错误

#include <iostream>
#include <cstring>
#include <unordered_set>
#include <vector>
using namespace std;

const int N = 510;
int a[N], b[N];

int main()
{
    int m, n, k, q;
    cin >> m >> n >> k;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[i] = x, b[i] = y;
    }
    cin >> q;
    while (q --)
    {
        unordered_set<int> hset;
        vector<int> res(m + 1);
        for(int i = 1; i <= m; i++)
        {
            cin >> res[i];
            hset.insert(res[i]);
        }
        if (hset.size() < k) puts("Error: Too few species.");
        else if (hset.size() > k) puts("Error: Too many species.");
        else{
            bool flag = true;
            for(int i = 0; i < n; i++)
            {
                int x = a[i], y = b[i];
                if (res[x] == res[y])
                {
                    flag = false;
                    break;
                }
            }
            if (flag) puts("Yes");
            else puts("No");
        }
    }
}