Hdu4115 Eliminate the Conflict 【2-SAT、3 -＞ 2】

本文主要是介绍Hdu4115 Eliminate the Conflict 【2-SAT、3 -＞ 2】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Eliminate the Conflict

题意

$Alice$ 和 $Bob$ 在玩剪刀石头布，一共 $n$ 轮。但 $Alice$ 已经提前得知了 $Bob$ 每一轮将要出的结果（$1$ 表示石头、$2$ 表示布、$3$ 表示剪刀）
为了不让 $Alice$ 赢得太轻松，$Bob$ 给 $Alice$ 提出了 $m$ 个限制条件：

• $u,v,k$：如果 $k=0$，$Alice$ 必须在 $u,v$ 两轮中出相同的手势，
  如果 $k=1$，$Alice$ 必须在 $u,v$ 两轮中出不同的手势

问 $Alice$ 能否在遵守所有限制条件的情况下，至少不输给 $Bob$？
（我不是想赢，我只是不想输）

思路

如果我们将三种手势的序号减一，那么可以发现三种手势的序号，能赢当前的手势 $i$ 的序号正好是 $(i+1)mod3$，那么我们在提前知道 $b_i$（$Bob$ 每轮要出的手势）的前提下，我们这一轮只能出 $i$ 或 $(i+1)mod3$，这样子才能保证不输，这样子就将 $3-SAT\to 2-SAT$

再来考虑限制，对于相同和不同的情况，分情况讨论一下，要连的边右点多

// Problem: Eliminate the Conflict
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=4115
// Memory Limit: 32 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long longconst int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;typedef long long ll;struct TwoSat {int n; //属性数量std::vector<std::vector<int>> e;std::vector<bool> ans;TwoSat(int n) : n(n), e(2 * n), ans(n) {} //下标从0开始/* 建边表示 u为f 且 v为g */void addedge(int u, bool f, int v, bool g) { //原变量和反变量相邻放e[2 * u + !f].push_back(2 * v + g); //反变量在偶数位置，原变量在奇数位置e[2 * v + !g].push_back(2 * u + f);}void adde(int u, int f, int v, int g){e[2 * u + f].push_back(2 * v + g);}bool satisfiable() {std::vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);std::vector<int> stk;int now = 0, cnt = 0;std::function<void(int)> tarjan = [&](int u) {stk.push_back(u);dfn[u] = low[u] = now++;for (auto v : e[u]) {if (dfn[v] == -1) {tarjan(v);low[u] = std::min(low[u], low[v]);} else if (id[v] == -1) {low[u] = std::min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {int v;do {v = stk.back();stk.pop_back();id[v] = cnt;} while (v != u);++cnt;}};for (int i = 0; i < 2 * n; ++i) if (dfn[i] == -1) tarjan(i);for (int i = 0; i < n; ++i) {if (id[2 * i] == id[2 * i + 1]) return false;ans[i] = id[2 * i] > id[2 * i + 1]; //取依赖性更高的那个}return true;}std::vector<bool> get_ans() { return ans; }
};int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int _;std::cin >>_;fore(test, 1, _ + 1){std::cout << "Case #" << test << ": ";int n, m;std::cin >> n >> m;TwoSat ts(n);std::vector<int> b(n);std::vector<std::pair<int, int>> c(n); //在这一轮能出的两种手势fore(i, 0, n){std::cin >> b[i];--b[i];c[i] = {(b[i] + 1) % 3, b[i]};}while(m--){int u, v, k;std::cin >> u >> v >> k;--u;--v;if(!k){ //sameif(c[u] == c[v]){ts.addedge(u, 1, v, 0);ts.addedge(u, 0, v, 1);}else{if(c[u].fi == c[v].fi){ts.adde(u, 1, u, 0);ts.adde(v, 1, v, 0);ts.adde(u, 0, v, 0);ts.adde(v, 0, u, 0);}else if(c[u].se == c[v].se){ts.adde(u, 0, u, 1);ts.adde(v, 0, v, 1);ts.adde(u, 1, v, 1);ts.adde(v, 1, u, 1);}else if(c[u].fi == c[v].se){ts.adde(u, 1, u, 0);ts.adde(v, 0, v, 1);ts.adde(u, 0, v, 1);ts.adde(v, 1, u, 0);}else{ts.adde(u, 0, u, 1);ts.adde(v, 1, v, 0);ts.adde(u, 1, v, 0);ts.adde(v, 0, u, 1);}}}else{ //differentif(c[u] == c[v]){ts.addedge(u, 0, v, 0);ts.addedge(u, 1, v, 1);}else{if(c[u].fi == c[v].fi){ts.addedge(u, 1, v, 1);}else if(c[u].se == c[v].se){ts.addedge(u, 0, v, 0);}else if(c[u].fi == c[v].se){ts.addedge(u, 1, v, 0);}else{ts.addedge(u, 0, v, 1);}}}}if(ts.satisfiable())	std::cout << "yes\n";else std::cout << "no\n";}return 0; 
}

这篇关于Hdu4115 Eliminate the Conflict 【2-SAT、3 -＞ 2】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---