题解|[ 题解 ] [ JZOJ5777 ] 小 x 玩游戏 c++|算法|算法

题面
今天，小 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(能过)
【题解|[ 题解 ] [ JZOJ5777 ] 小 x 玩游戏】Code（C++11）: 4068KB 248ms

#include #include #include #include const int MAX_N = 4e3 + 50; using pii = std::pair; std::unordered_map::string, int> 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 << "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; }