Acwing 405. 将他们分好队

大型补档计划

看到分成两组，想到二分图判定 + 染色。

二分图的特点是两个有矛盾的点连一条边，考虑在这道题中，如果 $a, b$ 中有一个人不认识对方（或者两个人互不认识），就不可能分在一组，可以在 $(a, b)$ 连一条无向边。

但是由于图不连通，每个联通块染色跑出两种颜色的数量 $c_1, c_2$ 后（跑不出来无解），让两队数量接近，等价于让一队的数量 $ <= \frac{N}{2}$ 且最大，我们可以把这两个当做一组，把 $cnt$ 个联通块当做物品，做分组背包选出一队的人员（并且强制选择），因为答案输出任意一组方案，倒序递推出答案即可。

切忌强制转移！因为不强制转移可能出现一组都不选，而题目要求每个队员必须在一队（会 WA 53）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int N = 105;

int n, c1, c2, cnt, col[N], vis[N];

int f[N][N], a[N][N], b[N][N], d[N];

vector<int> ans[2];

bool g[N][N];

bool dfs(int u, int t, int c) {

	col[u] = c, vis[u] = t;

	c == 1 ? c1++ : c2++;

	for (int v = 1; v <= n; v++) {

		if (v != u && (!g[u][v] || !g[v][u])) {

			if (!col[v]) {

				if (!dfs(v, t, 3 - c)) return false;

			} else if(col[v] == c) return false;

		}

	}

	return true;

}

void work(int i, int j) {

	if (i == 0) return;

	if (b[i][j]) d[i] = b[i][j];

	work(i - 1, a[i][j]);

}

int main() {

    memset(f, 0xcf, sizeof f);

    f[0][0] = 0;

	scanf("%d", &n);

	for (int i = 1, x; i <= n; i++) {

		while (scanf("%d", &x), x) {

			g[i][x] = true;

		}

	}

	int V = n >> 1;

	for (int i = 1; i <= n; i++) {

		if (!vis[i]) {

			c1 = 0, c2 = 0;

			if(!dfs(i, ++cnt, 1)) {

			    puts("No solution");

			    return 0;

			}

			for (int j = V; j >= 0; j--) {

				if (j >= c1 && f[cnt - 1][j - c1] + c1 >= f[cnt][j]) {

					f[cnt][j] = f[cnt - 1][j - c1] + c1;

					a[cnt][j] = j - c1, b[cnt][j] = 1;

				}

				if (j >= c2 && f[cnt - 1][j - c2] + c2 >= f[cnt][j]) {

					f[cnt][j] = f[cnt - 1][j - c2] + c2;

					a[cnt][j] = j - c2, b[cnt][j] = 2;

				}

			}

		}

	}

	int res = 0, t = -1;

	for (int i = 0; i <= V; i++)

	    if (f[cnt][i] > res) res = f[cnt][i], t = i;

	work(cnt, t);

	for (int i = 1; i <= n; i++) {

	    if ((col[i] == 1 && d[vis[i]] == 1) || (col[i] == 2 && d[vis[i]] == 2)) ans[0].push_back(i);

	    else ans[1].push_back(i);

	}

	for (int i = 0; i < 2; i++) {

	    printf("%d ", ans[i].size());

	    for (int j = 0; j < ans[i].size(); j++) printf("%d ", ans[i][j]);

	    puts("");

	}

	return 0;

}

巴特西

Acwing 405. 将他们分好队

最新文章

热门文章