hdu 1814 Peaceful Commission

本文从WordPress迁移而来, 查看全部WordPress迁移文章

2-sat输出字典序最小的解

题意:略

做法不是普通的2-sat做法,2-sat构图后直接用dfs出答案。

dfs的方法和道理如下: 因为字典序最小,所有优先从编号最小的点出发dfs。

从一个点出发,如果没染色,就染成红色,对立点然后蓝色,认为该点是解中的一个点。

如果本次dfs中发现一个点已经染色就讨论:如果是蓝色,说明是个对立点,一定是刚才dfs中或之前某次dfs中被染的,如果选了这个蓝点,必将和这个蓝点的对立点矛盾,要抛弃。

为什么要抛弃蓝点不抛弃红点呢? 因为抛弃了红点其实意味着要抛弃之前一系列的红点,而之前一系列的红点的字典序必定更小,不能抛弃,所以只能抛弃当前的蓝点了,抛弃蓝点就要返回,这是个失败的返回。如果遇到的点被染色了而且是红色,那么说明之前已经选了这个点,而且从这个点出发也已经遍历过了,所以也可以返回,相当于剪枝了,接着返回,这是个成功的返回。

返回后,看看是因为什么返回的,如果是失败的返回,说明这次dfs是失败的,这次dfs过程中染的点都不合法,所以要把这次dfs中染的点全部染回白色(因此在dfs过程中要记录下去了哪些点,到时候染回来)。

如果从一个点出发dfs是失败,那么就从它的对立点出发再dfs一次,如果两个点都失败,说明整个2-sat无解,因为一对对立点必须选一个

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 16010
#define M 100010
#define RED 1
#define BLUE 2
#define WHITE 0
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,m,tot,len,head[N],color[N],list[N];
struct edge{
int u,v,next;
}e[M];

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

bool dfs(int u){
if(color[u] == BLUE) return false;
if(color[u] == RED) return true;
color[u] = RED;
color[u^1] = BLUE;
list[len++] = u;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
bool res = dfs(v);
if(!res) return false;
}
return true;
}

bool check(){
cl(color,WHITE);
for(int i = 0; i < n; i++)
if(color[i] == WHITE){
len = 0;
bool res = dfs(i);
if(!res){
for(int k = 0; k < len; k++)
color[list[k]] = color[list[k]^1] = WHITE;
res = dfs(i^1);
if(!res) return false;
}
}
return true;
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
tot = 0; n <<= 1;
cl(head,-1);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
u--; v--;
add(u,v^1); add(v,u^1);
}
if(!check())
puts("NIE");
else
for(int i = 0; i < n; i++)
if(color[i] == RED)
printf("%d\n",i+1);
}
return 0;
}