MYF

HDU 3062 Party

题目链接

HDU 3062

题目类型:2-SAT

题目分析

题目大意

有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n 个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席?

解析

2-SAT问题解决的范围为A满足条件或B满足条件。对于这道题来讲,就是保证给定的两个人不同时参加,e.g.a的妻子和b的丈夫有矛盾,那么我们可以令a的丈夫参加或者b的妻子参加,两者满足一个条件时就不会发生矛盾。按照这个方法增加限定条件即可。

代码

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;
struct 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)
{
this->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;
}
}ts;
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
ts.init(n);
while(m--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
ts.add_clause(a, 1-c, b, 1-d);
}
if(ts.solve()) puts("YES");
else puts("NO");
}
}