P5782 [POI 2001] 和平委员会

P5782 [POI 2001] 和平委员会

大意

\(n\) 个党派，每个党派 \(i\) 有两个代表 \(2i,2i + 1\)，然后给你 \(m\) 对互相厌恶的关系，求方案。

思路

那么，相当于每个党派的两个代表就是两种情况，然后直接按其说的厌恶的关系建边跑 \(\text{2 - SAT}\) 即可。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;inline int get_id(int x) {x--;return x;
}bool dfs(int u) {if (vis[u ^ 1]) return false;if (vis[u]) return true;vis[u] = true;S[c++] = u;for (int v : g[u]) {if (!dfs(v)) return false;}return true;
}bool Two_SAT() {memset(vis, 0, sizeof(vis));for (int i = 0; i < 2 * n; i += 2) {if (!vis[i] && !vis[i + 1]) {c = 0;if (!dfs(i)) {while (c > 0) vis[S[--c]] = false;if (!dfs(i + 1)) {return false;}}}}return true;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;int u = get_id(a);int v = get_id(b);g[u].push_back(v ^ 1);g[v].push_back(u ^ 1);}if (!Two_SAT()) {cout << "NIE" << endl;} else {vector<int> ans;for (int i = 0; i < 2 * n; i += 2) {if (vis[i]) {ans.push_back(i + 1);} else {ans.push_back(i + 2);}}sort(ans.begin(), ans.end());for (int x : ans) {cout << x << endl;}}return 0;
}