咸宁公司做网站,常州手机网站效果,重庆微网站建设,爱站seo工具包免费版UVa1086/LA4452 The Minister’s Major Mess 题目链接题意分析AC 代码 题目链接 本题是2009年icpc世界总决赛的H题
题意 n#xff08;n≤500#xff09;个人对m#xff08;m≤100#xff09;个方案投票。每个人最多只能对其中的4个方案投票#xff08;其他相当于弃权票n≤500个人对mm≤100个方案投票。每个人最多只能对其中的4个方案投票其他相当于弃权票每一票要么支持要么反对。问是否存在一个最终决定对每个方案要么采用要么否定使得每个投票人都有超过一半的建议被采纳。在所有可能的最终决定中哪些方案的态度是确定的
分析 每个方案要么采用要么否定可以往2-SAT上想对每个投了3个或4个方案的人其某个投票如果被否定则剩下的投票一定要被采纳对投了1个或2个方案的人其投票必须都被采纳说明部分结点的初始值固定。 本题不是对2-SAT问题找一个可行解而是要判断每一个方案的两个取值可能的情况两个值采纳/否定都取不到无解仅取得到一个答案的此位输出y/n都可能取到则答案的此位输出?。那就需要对每个结点做dfs/bfs看是否出现矛盾不矛盾则此结点代表的值可取得否则此结点代表的值不可取得。
AC 代码
#include iostream
#include cstring
using namespace std;#define N 206
int g[N][N], c[N], s[N], x[N], v[4], p, m, n, t, kase 0; bool vis[N][N], f[N];bool check(int u, int r) {s[p] u; x[u] r;while (p) {u s[--p];for (int i0, v; ic[u]; i) if (x[v g[u][i]] ! r) {if (!f[v] || x[v^1] r) return false;s[p] v; x[v] r;}}return true;
}void solve() {t (m1)1; memset(c, 0, sizeof(c)); memset(f, 1, sizeof(f));memset(vis, 0, sizeof(vis)); memset(x, 0, sizeof(x));for (int i0; in; i) {int cc; cin cc;for (int j0; jcc; j) {int x; char ch; cin x ch; v[j] x1 | chn;}if (cc 2) {for (int j0; jcc; j) for (int k0, xv[j]^1, y; kcc; k) if (j!k !vis[x][yv[k]])g[x][c[x]] y, vis[x][y] true;} else for (int j0; jcc; j) f[v[j]^1] false;}cout Case kase : ;for (int u2; ut; u) {if (f[u]) p 0, f[u] check(u, u);if (!f[u] !f[u^1]) {cout impossible endl; return;}}for (int i2; it; i2) cout (f[i] f[i^1] ? ? : (f[i] ? y : n));cout endl;
}int main() {while (cin m n m) solve();return 0;
}
