二分图染色+线性dp，码蹄集OJ-聚会

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

码蹄集

---

二、解题报告

1、思路分析

看到题会有一种冲动抽象成图论模型

注意到将 互相不认识 的 连边，是否存在合法解就相当于是否满足二分图

这个可以染色法解决：二分图判定与染色法：理论与代码实现,-CSDN博客

然后注意到原图会有很多连通块，每个连通块内只要有一个点的颜色确定，那么剩下的全都确定了

于是考虑dp

定义状态 f(i, j, k) 为 前 i 个连通块，j 个染成 颜色 k 是否可行

那么 f(i, j, k) = f(i, j, k) || f(i - 1, j - siz(i, k), k)，siz(i, k) 为 第 i 个联通块中 颜色为k的节点数目

值得注意的是，一个联通块的两种颜色可以互换的，所以刷表法转移的时候应该这么转移：

                f[i + 1][j][k] |= f[i][j - siz[i][k]][k];
                f[i + 1][j][k ^ 1] |= f[i][j - siz[i][k]][k ^ 1];

2、复杂度

时间复杂度： O(N^2)空间复杂度：O(N^2)

3、代码详解

 ​

#include<bits/stdc++.h>
const int N = 512;int g[N][N];
bool f[N + 1][N + 1][2];int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {std::cin >> g[i][j];}}std::vector<std::vector<int>> adj(n);for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (!g[i][j] || !g[j][i]) {adj[i].push_back(j);adj[j].push_back(i);}}}std::vector<std::array<int, 2>> siz;std::vector<int> col(n, -1);auto dfs = [&](auto && self, int u, int c) -> bool {col[u] = c;++ siz.back()[c];for (int v : adj[u]) {if (col[u] == col[v]) {return false;}if (col[v] == -1 && !self(self, v, c ^ 1))return false;}return true;};for (int i = 0; i < n; i++) {if (~col[i])continue;siz.push_back({0, 0});if (!dfs(dfs, i, 0)) {std::cout << "No" << '\n';return 0;}}f[0][0][0] = true;f[0][0][1] = true;int M = n / 2;const int m = siz.size();for (int i = 0; i < m; i++) {for (int k = 0; k < 2; ++ k) {for (int j = siz[i][k]; j <= M; j++) {f[i + 1][j][k] |= f[i][j - siz[i][k]][k];f[i + 1][j][k ^ 1] |= f[i][j - siz[i][k]][k ^ 1];}}}int ans = 0;for (int j = M; j >= 1; j--) {if (f[m][j][0] || f[m][j][1]) {ans = n - j;break;}}std::cout << "Yes" << '\n';std::cout << ans << '\n';    return 0;
}