首页 > 代码库 > HDU 4421 Bit Magic(2-sat)
HDU 4421 Bit Magic(2-sat)
HDU 4421 Bit Magic
题目链接
题意:就根据题目,给定b数组,看能不能构造出一个符合的a数组
思路:把每个数字的每个二进制位单独考虑,就变成一个2-sat题目了,根据题目中的式子建立2-sat的边,然后每一位跑2-sat,如果每位都符合,就是YES,如果有一位不符合就是NO
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; const int MAXNODE = 505; struct TwoSet { int n; vector<int> g[MAXNODE * 2]; bool mark[MAXNODE * 2]; int S[MAXNODE * 2], sn; void init(int tot) { n = tot * 2; for (int i = 0; i < n; i += 2) { g[i].clear(); g[i^1].clear(); } memset(mark, false, sizeof(mark)); } void add_Edge(int u, int uval, int v, int vval) { u = u * 2 + uval; v = v * 2 + vval; g[u^1].push_back(v); g[v^1].push_back(u); } void delete_Edge(int u, int uval, int v, int vval) { u = u * 2 + uval; v = v * 2 + vval; g[u^1].pop_back(); g[v^1].pop_back(); } bool dfs(int u) { if (mark[u^1]) return false; if (mark[u]) return true; mark[u] = true; S[sn++] = u; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!dfs(v)) return false; } return true; } bool solve() { for (int i = 0; i < n; i += 2) { if (!mark[i] && !mark[i + 1]) { sn = 0; if (!dfs(i)){ for (int j = 0; j < sn; j++) mark[S[j]] = false; sn = 0; if (!dfs(i + 1)) return false; } } } return true; } } gao; const int N = 505; int n, b[N][N]; bool solve() { for (int k = 0; k < 31; k++) { gao.init(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { int tmp = (b[i][j]>>k)&1; if (i == j) { if (tmp) return false; } else if (i % 2 == 1 && j % 2 == 1) { if (tmp) gao.add_Edge(i, tmp, j, tmp); else { gao.add_Edge(i, tmp, i, tmp); gao.add_Edge(j, tmp, j, tmp); } } else if (i % 2 == 0 && j % 2 == 0) { if (tmp) { gao.add_Edge(i, tmp, i, tmp); gao.add_Edge(j, tmp, j, tmp); } else gao.add_Edge(i, tmp, j, tmp); } else { if (tmp) { gao.add_Edge(i, tmp, j, tmp); gao.add_Edge(i, !tmp, j, !tmp); } else { gao.add_Edge(i, tmp, j, !tmp); gao.add_Edge(i, !tmp, j, tmp); } } } if (!gao.solve()) return false; } return true; } int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &b[i][j]); printf("%s\n", solve() ? "YES" : "NO"); } return 0; }
HDU 4421 Bit Magic(2-sat)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。