[ 题解 ] [ 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 s1​，s2​，表示 s 1 s_1 s1​ 杀了 s 2 s_2 s2​，其中 s 1 ， s 2 s_1，s_2 s1​，s2​ 的长度均不超过 10 10 10（数据保证两个字符串都由小写字母组成）。注意一个人可以被击杀多次、一个人可以被曾经杀死过的人给杀死。

输出
总共有 t t t 行，每行一个 YES 或 NO，YES 表示符合题目条件，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 t≤10，n≤2000，m≤100000。
数据保证不会有矛盾的关系。

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

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

Code（C++11）: 4068KB 248ms

#include 
#include 
#include 
#include 

const int MAX_N = 4e3 + 50;

using pii = std::pair;

std::unordered_map id;
int id_cnt;

std::vector g[MAX_N];
std::vector 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 << "NOn";
            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;
}