[ 题解 ] [ JZOJ5777 ] 小 x 玩游戏

题面

今天,小 x 因为太无聊,就在玩游戏。这个游戏有两个队伍,然后他们在游戏里面打来打去。

但小 x 遇到了难题。他不知道自己的队友是谁。他只知道总共有两个队伍,每队有 n n n 个人和很多组击杀情况。他想问你,现在他能否知道两个队伍分别有谁。你可以帮助小 x 吗?由于小 x 是个游戏狂魔,所以他玩了很多局游戏。

输入
第一行有一个 t t t,表示小 x 共玩了 t t t 局游戏。

接下来有 t t t 组数据,每组数据第一行有一个 n , m n, m n,m,表示每队有 n n n 个人,有 m m m 组击杀情况,接下来 m m m 行每行两个字符串 s 1 , s 2 s_1,s_2 s1s2,表示 s 1 s_1 s1 杀了 s 2 s_2 s2,其中 s 1 , s 2 s_1,s_2 s1s2 的长度均不超过 10 10 10(数据保证两个字符串都由小写字母组成)。注意一个人可以被击杀多次、一个人可以被曾经杀死过的人给杀死。

输出
总共有 t t t 行,每行一个 YESNOYES 表示符合题目条件,NO 表示不符合。

Example
Input

1
2 3
a b
c d
a d

Output

YES

数据范围
对于 100 100% 100 的数据, t ≤ 10 , n ≤ 2000 , m ≤ 100000 t \leq 10,n \leq 2000,m \leq 100000 t10n2000m100000
数据保证不会有矛盾的关系。

题解

对每个联通块染色,得到两种颜色的个数。
把所有的个数都塞到一个列表里(颜色不重要,当作没有就好)
暴力枚举,取列表中一半的数,看有没有可能使得取的一半的和与另一半相等。
可能就 YES
不可能就 NO

复杂度:联通块个数的阶乘(少一些) O ( 能 过 ) O(能过) O()

Code(C++11): 4068KB 248ms

#include 
#include 
#include 
#include 

const int MAX_N = 4e3 + 50;

using pii = std::pair<int, int>;

std::unordered_map<std::string, int> id;
int id_cnt;

std::vector<int> g[MAX_N];
std::vector<int> nums;
int tot;

int color[MAX_N];

void init()
{
     
    id.clear();
    id_cnt = 0;
    for (int _i = 0; _i < MAX_N; _i++)
        g[_i].clear();
    nums.clear();
    tot = 0;
    memset(color, 0, sizeof(color));
}

pii dfs(int u)
{
     
    pii res{
     0, 0};
    if (color[u] == -1)
        res.first = 1;
    else
        res.second = 1;

    for (auto v : g[u])
    {
     
        if (color[v] == 0)
        {
     
            color[v] = (color[u] == 1 ? -1 : 1);
            const auto ret = dfs(v);
            res.first += ret.first;
            res.second += ret.second;
        }
    }

    return res;
}

bool dfs2(std::size_t step, std::size_t last, int sum, const std::size_t size)
{
     
    if (step == size / 2)
        return 2 * sum == tot;

    for (std::size_t i = last + 1; i < size; i++)
    {
     
        const bool ret = dfs2(step + 1, i, sum + nums[i], size);
        if (ret)
            return true;
    }

    return false;
}

int main()
{
     
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;

    for (int _i = 0; _i < t; _i++)
    {
     
        int n, m;
        std::cin >> n >> m;

        init();

        for (int _i = 0; _i < m; _i++)
        {
     
            std::string u, v;
            std::cin >> u >> v;

            if (!id[u])
                id[u] = ++id_cnt;
            if (!id[v])
				id[v] = ++id_cnt;

            g[id[u]].emplace_back(id[v]);
            g[id[v]].emplace_back(id[u]);
        }

        if (2 * n - id_cnt >= 2)
        {
     
            std::cout << "NO\n";
            continue;
        }

        for (int i = 1; i <= id_cnt; i++)
        {
     
            if (color[i] == 0)
            {
     
                color[i] = 1;
                const auto ret = dfs(i);
                tot += ret.first + ret.second;
                nums.emplace_back(ret.first);
                nums.emplace_back(ret.second);
            }
        }

        const bool ret = dfs2(0, -1, 0, nums.size());
        std::cout << (ret ? "YES" : "NO") << "\n";
    }

    return 0;
}

你可能感兴趣的