poj 3905 perfect election(简单2-sat)
http://poj.org/problem?id=3905
题意:
这里有1到n个人正在进行议员选举,每个人有2种结果,选上(0),未选上(1).现在的问题是,有m个选民的议员,结果必须符合这m条意愿,问你是否存在这种选举结果.
分析:
由于每条意愿都是或的关系.则直接用2-sat添加对应边即可.
简单2-sat问题,注意把候选人序号改成0到n-1即可.
ac代码:
#include#include#include#includeusing namespace std;const int maxn = 1000+10;struct twosat{ int n; vector g[maxn*2]; int s[maxn*2],c; bool mark[maxn*2]; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x]= true; s[c++]=x; for(int i=0;in=n; for(int i=0;i