[Non] - 选举
大意
给定 \(N\) 个候选人 \(\{1,2,\dots,N\}\) 和 \(M\) 个形如 \(\pm i \pm j\)（\(1 \le i,j \le N\)）的民意调查约束，判断是否存在对每个候选人「当选/落选」的状态分配方案，使得该方案满足所有约束条件。若存在则输出 \(1\)，否则输出 \(0\)。
- \(+i+j\) → \(x_i \lor x_j\)（至少一个当选）
- \(-i-j\) → \(\neg x_i \lor \neg x_j\)（至少一个落选）
- \(+i-j\) → \(x_i \lor \neg x_j\)（\(i\) 当选 或 \(j\) 落选）
- \(-i+j\) → \(\neg x_i \lor x_j\)（\(i\) 落选 或 \(j\) 当选）
思路
对于这个题目，显然的，\(\text{2 - SAT}\) 直接秒了。
代码
#include<iostream>
#include<vector>
using namespace std;const int MAXN = 1005;
int n, m;
vector<int> g[MAXN * 2];
bool vis[MAXN * 2];
int S[MAXN * 2], c = 0;bool dfs(int u){if(vis[u ^ 1]){return false;}if(vis[u]) return true;vis[u] = true;S[c ++] = u;for(int i = 0;i < g[u].size();i ++){int v = g[u][i];if(!dfs(v)){return false;}}return true;
}bool judge(){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(0);cin.tie(0);while(cin >> n >> m){for(int i = 0;i <= 2 * n - 1;i ++){if(!g[i].empty()) g[i].clear();vis[i] = false;}for(int i = 1;i <= m;i ++){string s1, s2;cin >> s1 >> s2;int u = stoi(s1.substr(1)); u --;int v = stoi(s2.substr(1)); v --;if(s1[0] == '+' && s2[0] == '+'){g[u * 2 + 1].push_back(v * 2);g[v * 2 + 1].push_back(u * 2);}else if(s1[0] == '-' && s2[0] == '-'){g[u * 2].push_back(v * 2 + 1);g[v * 2].push_back(u * 2 + 1);}else if(s1[0] == '+' && s2[0] == '-'){g[u * 2 + 1].push_back(v * 2 + 1);g[v * 2].push_back(u * 2);}else{g[u * 2].push_back(v * 2);g[v * 2 + 1].push_back(u * 2 + 1);}}if(judge()){cout << 1 << '\n';}else{cout << 0 << '\n';}}return 0;
}