首页 > 代码库 > hdu1814 Peaceful Commission,2-sat
hdu1814 Peaceful Commission,2-sat
题目大意:一国有n个党派,每个党派在议会中都有2个代表,现要组建和平委员会,要从每个党派在议会的代表中选出1人,一共n人组成和平委员会。已知有一些代表之间存在仇恨,也就是说他们不能同时被选为和平委员会的成员,现要你判断满足要求的和平委员会能否创立?如果能,请任意给出一种方案。
2-sat问题
#include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int maxn = 10005; int n, m; vector<int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2], top; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x] = true; S[top++] = x; for(int i=0; i<G[x].size(); ++i) if(!dfs(G[x][i])) return false; return true; } bool TwoSat() { memset(mark, 0, sizeof mark ); for(int i=0; i<n; i += 2) { if(!mark[i] && !mark[i^1]) { top = 0; if(!dfs(i)) { while(top) mark[S[--top]] = false; if(!dfs(i^1)) return false; } } } return true; } int main() { int u, v; while(~scanf("%d%d", &n, &m)) { n *= 2; for(int i=0; i<n; ++i) G[i].clear(); while(m--) { scanf("%d%d", &u, &v); u--; v--; G[u].push_back(v^1); G[v].push_back(u^1); } if(TwoSat()) { for(int i=0; i<n; i+=2) if(mark[i]) printf("%d\n", i+1); else printf("%d\n", (i^1)+1); } else printf("NIE\n"); } return 0; }
hdu1814 Peaceful Commission,2-sat
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。