首页 > 代码库 > UVA 1086 - The Ministers' Major Mess(2-sat)
UVA 1086 - The Ministers' Major Mess(2-sat)
UVA 1086 - The Ministers‘ Major Mess
题目链接
题意:有n个方案,每个人投票,一个人最多投4张票,现在要有一个方案,使得满足所有人投票方案中有超过一半被满足,输出方案的对错,如果一个方案对错都可以,就输出?
思路:明显是二分图,一开始想错了,想从正着去把条件式化简,根本不可行
正确的做法是,反过来想,因为最多4张票并且超过1半,如果反过来想选哪些方案不满足,那么就只有1和0的情况,就很容易构造表达式了,然后就是2-sat,对于?的情况,只要遍历一遍,每个位置再加一条和原来条件相反的边然后做一次2-sat,如果还满足就是?,如果不满足就是位置的y或n
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; const int MAXNODE = 105; 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 = 105; int n, m; int a[5]; bool b[5], save[N]; int bitcount(int x) { int ans = 0; while (x) { ans += (x&1); x >>= 1; } return ans; } int main() { int cas = 0; while (~scanf("%d%d", &n, &m) && n || m) { int k; gao.init(n); while (m--) { scanf("%d", &k); char c; for (int i = 0; i < k; i++) { scanf("%d %c", &a[i], &c); a[i]--; if (c == 'y') b[i] = true; else b[i] = false; } if (k <= 2) { for (int i = 0; i < k; i++) gao.add_Edge(a[i], b[i], a[i], b[i]); } else { for (int i = 0; i < k; i++) { for (int j = i + 1; j < k; j++) { gao.add_Edge(a[i], b[i], a[j], b[j]); } } } } printf("Case %d: ", ++cas); if (!gao.solve()) printf("impossible\n"); else { for (int i = 0; i < n; i++) save[i] = gao.mark[i * 2 + 1]; for (int i = 0; i < n; i++) { memset(gao.mark, false, sizeof(gao.mark)); gao.add_Edge(i, !save[i], i, !save[i]); if (gao.solve()) printf("?"); else printf("%c", save[i] ? 'y' : 'n'); gao.delete_Edge(i, !save[i], i, !save[i]); } printf("\n"); } } return 0; }
UVA 1086 - The Ministers' Major Mess(2-sat)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。