例题 9-19 团队分组（Team them up!, ACM/ICPC NEERC 2001, UVa1627)

本文主要是介绍例题 9-19 团队分组（Team them up!, ACM/ICPC NEERC 2001, UVa1627)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1627
分类：0-1背包
备注：二分图，背包变体

按照紫书的思路，将不互相认识的连在一起，这样形成连通图必须要能够变为二分图，否则不合题意，然后黑白染色，两种颜色对应两个分组，互换一下分组，组员数量的差值就会变化，可以据此来进行DP。

开始以为，只要对每个连通图看两种情况即可，每次都求出最优结果。WA了之后再看别人的解法，仔细一想发现直接这样的状态转移是一种贪心的做法。在洛谷上有一句总结：对付这种“01背包”，常见的状态设定是：用 dp[i][j] 表示前 i 个物品是否能凑出 j 的价值。根据这种思路，就才能对全局最优都有把握。

还是挺难的一个题，像是二分图这里估计自己都想不到。

#include <bits/stdc++.h>
using namespace std;const int N = 100 + 5;int t, n, tot, co[N], g[N][N], diff[N], dp[N][N * 2];
vector<int> e[N][2];bool dfs(int u, int o) {co[u] = o;e[tot][o].push_back(u);for (int v = 1; v <= n; v++) {if (u == v || (g[u][v] && g[v][u])) continue;if (co[v] != -1 && co[v] == co[u]) return false;if (co[v] == -1 && !dfs(v, o ^ 1)) return false;}return true;
}bool init() {memset(co, -1, sizeof(co));tot = 0;for (int i = 1; i <= n; i++) {if (co[i] != -1) continue;e[tot][0].clear();e[tot][1].clear();if (!dfs(i, 0)) return false;diff[tot++] = e[tot][0].size() - e[tot][1].size();}return true;
}int main(void) {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);scanf("%d", &t);for (int kase = 1; kase <= t; kase++) {if (kase != 1) puts("");scanf("%d", &n);memset(g, 0, sizeof(g));for (int i = 1; i <= n; i++) {int x;while (~scanf("%d", &x) && x != 0) {g[i][x] = 1;}}if (!init()) puts("No solution");else {memset(dp, 0, sizeof(dp));dp[0][0 + n] = 1;for (int i = 0; i < tot; i++) {for (int j = -n; j <= n; j++) {if (dp[i][j + n]) {dp[i + 1][j + n + diff[i]] = 1;dp[i + 1][j + n - diff[i]] = 1;}}}int ans;for (ans = 0; ans <= n; ans++) {if (dp[tot][n + ans]) break;if (dp[tot][n - ans]) {ans *= -1; break;}}vector<int> team[2];for (int i = tot - 1, o; i >= 0; i--) {if (dp[i][ans - diff[i] + n]) {o = 0; ans -= diff[i];} else {o = 1; ans += diff[i];}for (int j = 0; j < e[i][o].size(); j++)team[0].push_back(e[i][o][j]);for (int j = 0; j < e[i][o ^ 1].size(); j++)team[1].push_back(e[i][o ^ 1][j]);}for (int i = 0; i < 2; i++) {printf("%d", team[i].size());for (int j = 0; j < team[i].size(); j++)printf(" %d", team[i][j]);puts("");}}}return 0;
}