MYF

POJ 3905 Perfect Election

Posted on | In | | Visitors

题目链接

POJ 3905

方法：2-SAT

题目分析

题目大意

这里有1到N个人正在进行议员选举,每个人有2种结果,选上(0),未选上(1).现在的问题是,有M个选民的议员,结果必须符合这M条意愿,问你是否存在这种选举结果.

注意，每个选民的意愿要求两个人，两个人分别选上或选不上，选上的话就是+x，不选上的话是-x，两个人之间的关系是或的关系

解析

用这道题来入门2-SAT算法好了。

2-SAT解决的是一系列双满足条件的问题，通过建立有向图，然后DFS跑出结果。

add_clause(x, xval, y, yval)表示的是(x == xval) || (y == yval)的关系。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <set>
#include <map>
#include <list>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define fre() freopen("data_in.txt","r",stdin); \
			  freopen("data_out.txt","w",stdout);
#define debug(x) cout<<"Debug : --- "<<x<<" ---"<<endl;
#define debug2(x,y) cout<<"Debug : --- "<<x<<" , "<<y<<" ---"<<endl;
#define debug3(x,y,z) cout<<"Debug : --- "<<x<<" , "<<y<<" , "<<z<<" ---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
const int maxn=100000+5;
namespace TwoSAT
{
	int n;//原始图的节点数(未翻倍)
	vector<int> G[maxn*2];//G[i]==j表示如果mark[i]=true,那么mark[j]也要=true
	bool mark[maxn*2];//标记
	int S[maxn*2],c;//S和c用来记录一次dfs遍历的所有节点编号

	void init(int _n)
	{
		n=_n;
		for(int i=0;i<2*n;i++) G[i].clear();
		memset(mark,0,sizeof(mark));
	}

	//加入(x,xval)或(y,yval)条件
	//xval=0表示假，yval=1表示真
	void add_clause(int x,int xval,int y,int yval)
	{
		x=x*2+xval;
		y=y*2+yval;
		G[x^1].push_back(y);
		G[y^1].push_back(x);
	}

	//从x执行dfs遍历,途径的所有点都标记
	//如果不能标记,那么返回false
	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;i<G[x].size();i++)
			if(!dfs(G[x][i])) return false;
		return true;
	}

	//判断当前2-SAT问题是否有解
	bool solve()
	{
		for(int i=0;i<2*n;i+=2)
		if(!mark[i] && !mark[i+1])
		{
			c=0;
			if(!dfs(i))
			{
				while(c>0) mark[S[--c]]=false;
				if(!dfs(i+1)) return false;
			}
		}
		return true;
	}
}
int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		TwoSAT::init(n);
		for(int i = 1 ; i <= m; i++){
			int u,v;
			scanf("%d %d",&u,&v);
			TwoSAT::add_clause(abs(u)-1, u>0?1:0, abs(v)-1, v>0?1:0);
		}
		if(TwoSAT::solve()) cout<<"1\n";
		else cout<<"0\n";
	}
}