poj 3683 Priest John's Busiest Day

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

2-sat

题意：有n对夫妻，它们要参加一个活动，数据中每个n行，每行两个时间，表示这对夫妻参加活动在这之间，但是在活动期间有一个典礼，这个典礼的时间是d，这个典礼只能在最开始或者或者最后的d时间内进行，例如总时间是8点到9点，典礼的时间是20分钟，那么典礼只能在2个时间段内进行，分别是8点到8点20分，或者8点40分到9点。你想参加完这n对夫妻的典礼，所以你要给每个夫妻的典礼安排一个时间，使得典礼时间不会冲突，这样你才能全部参加。如果无论怎么安排你都不能参加全部的典礼，那么就输出NO，否则的是输出YES，并且给出任意一种安排方案。不过注意输出的时候，要按照夫妻的顺序，给出它们对应的安排时间（即先输出第1对夫妻的时间，再第2对…..但是具体的时间是任意一组可行解即可）

1
2
3
4
5
每对夫妻的时间就是一对顶点
建图的时候需要一个二重循环，判断任意两对顶点（四个顶点）是否矛盾
两个点矛盾就是在它们公用了一段时间，好像u顶点的时间我[x,x+d],v顶点的时间是[v,v+dd]
如果这两个区间有交集，它们就是矛盾的,但只交了一个点不算
[08:00,08:30],[08:30,09:00],这不算矛盾它们可以共存

建图部分比较繁琐，因为这题的时间真的比较纠结，处理完这些前期工作，其实就是判断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
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define	N 2010
#define M 8000010 // 2 * N * N
#define cl memset
#define pb push_back

int lhh[N/2],lmm[N/2],ltot[N/2],rhh[N/2],rmm[N/2],rtot[N/2],dd[N/2];
int n,tot,head[N];
struct edge{
	int v,next;
}e[M];
vector<int>ver[N];	//重新建图
queue<int>que;    
vector<int>ans;		//保存一组可行解
int dfn[N],low[N],belong[N],stack[N],dcnt,bcnt,top; //强连通分量
bool ins[N];
int opp[N];			//重新建图后，记录每个顶点的对立顶点
int inde[N];		//统计DAG中每个点的入度，拓扑排序需要
int color[N];		//拓扑排序给图染色，0无色，1蓝色，2红色

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

inline bool ok(int *t){ //true表示两点无矛盾，false有矛盾
	if(t[1] <= t[2] || t[3] <= t[0]) 
		return true;
	return false;
}

void build(){ //建图
	tot = 0;
	cl(head,-1,sizeof(head));
	for(int i = 0; i < n ; i++)
		for(int j = i+1; j < n ; j++){
			int x,y,t[4];
			x = i<<1; y = j<<1;
			t[0] = ltot[i]; t[1] = ltot[i] + dd[i];
			t[2] = ltot[j]; t[3] = ltot[j] + dd[j];
			if( !ok(t) ){
				add(x,y|1); add(y,x|1);
			}
			y = j<<1|1;
			t[2] = rtot[j] - dd[j]; t[3] = rtot[j];
			if( !ok(t) ){
				add(x,y^1); add(y,x|1);
			}
			x = i<<1|1; y = j<<1;
			t[0] = rtot[i] - dd[i]; t[1] = rtot[i];
			t[2] = ltot[j]; t[3] = ltot[j] + dd[j];
			if( !ok(t) ){
				add(x,y|1); add(y,x^1);
			}
			y = j<<1|1;
			t[2] = rtot[j] - dd[j]; t[3] = rtot[j];
			if( !ok(t) ){
				add(x,y^1); add(y,x^1);
			}
		}
}

void tarjan(int u){
	dfn[u] = low[u] = ++dcnt;
	stack[++top] = u; ins[u] = true;
	for(int k = head[u]; k != -1; k = e[k].next){
		int v = e[k].v;
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(ins[v])
			low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u]){
		++bcnt;
		while(true){
			int x = stack[top--];
			ins[x] = false;
			belong[x] = bcnt;
			if(x == u) break;
		}
	}
}

void scc(){
	dcnt = bcnt = top = 0;
	cl(dfn,0,sizeof(dfn));
	cl(ins,false,sizeof(ins));
	for(int i = 0; i < 2*n; i++)
		if(!dfn[i])
			tarjan(i);
}

void rebuild(){ //缩点后重新建图
	for(int i = 1; i <= bcnt; i++){
		ver[i].clear();
		inde[i] = 0;
	}
	for(int i = 0; i < 2*n; i++)
		for(int k = head[i]; k != -1; k = e[k].next){
			int u = belong[i] , v = belong[e[k].v];
			if(u == v) continue;
			ver[v].pb(u); inde[u]++; //建逆图
		}
}

void topsort(){ //拓扑排序，给点染色
	cl(color,0,sizeof(color));
	while(!que.empty()) que.pop();
	for(int i = 1; i <= bcnt; i++)
		if(inde[i] == 0) que.push(i);
	while(!que.empty()){
		int u,v;
		u = que.front(); que.pop();
		if(color[u] == 0){ //还没染色的点，染成红色，对立点染蓝色
			color[u] = 2; color[opp[u]] = 1;
		}
		for(int i = 0; i < ver[u].size(); i++){
			v = ver[u][i]; inde[v]--;
			if(!inde[v]) que.push(v);
		}
	}
}

bool check(){ //判断是否存在可行解
	for(int i = 0; i < n ; i++){
		if(belong[i<<1] == belong[i<<1|1])
			return false;
		else{//记录每个点的对立点，记录的是它们所在的连通分量
			opp[belong[i<<1]] = belong[i<<1|1];
			opp[belong[i<<1|1]] = belong[i<<1];
		}
	}
	return true;
}

void Find_Ans(){ //根据染色结果找出可行解保存在ans中
	ans.clear();
	for(int u = 1; u <= bcnt; u++)
		if(color[u] == 2){
			for(int i = 0; i < 2*n; i++)
				if(belong[i] == u)
					ans.pb(i);
		}
	sort(ans.begin(),ans.end());
}

int main(){
	while(scanf("%d",&n)!=EOF){
		for(int i = 0; i < n; i++){
			scanf("%d:%d %d:%d %d",&lhh[i],&lmm[i],&rhh[i],&rmm[i],&dd[i]);
			ltot[i] = lhh[i] * 60 + lmm[i];
			rtot[i] = rhh[i] * 60 + rmm[i];
		}
		/*-------------------2-SAT模板部分----------------------*/
		build();		//根据矛盾关系建图，不同题目建图函数不同，但方法是一样的
		scc();			//对原图求强连通分量
		if(!check()){	//判断是否存在可行解
			puts("NO"); continue;	
		}
		rebuild();		//缩点后重新建图
		topsort();		//拓扑排序求一组可行解
		Find_Ans();		//根据拓扑结果找一组可行解
		/*-------------------2-SAT模板部分----------------------*/
		puts("YES");
		for(int i = 0; i < ans.size(); i++){
			int u = ans[i];
			if(u&1){
				printf("%02d:%02d ",(rtot[u>>1]-dd[u>>1])/60,(rtot[u>>1]-dd[u>>1])%60);
				printf("%02d:%02d\n",rhh[u>>1],rmm[u>>1]);
			}
			else{    
				printf("%02d:%02d ",lhh[u>>1],lmm[u>>1]);
				printf("%02d:%02d\n",(ltot[u>>1]+dd[u>>1])/60,(ltot[u>>1]+dd[u>>1])%60);
			}
		}
	}
	return 0;
}