题目大意:一个城镇里只有一个牧师,在国庆节这一天,他要为 n 对夫妇的婚礼祷告,这 n 对夫妇婚礼的开始时间 s 、结束时间 e 和祷告时间 d 不尽相同,但是祷告只能在每个婚礼的开始或结束时进行(如一个婚礼的开始时间为s , 结束时间为 e , 那么祷告的时间就为 s ~ s + d 或 e - d ~ e)。问:这个牧师是否能为所有的婚礼祷告,如果能,则输出为每个婚礼祷告的开始时间和结束时间。
解题思路:这是一道典型的2 - SAT 问题,很明显一个婚礼的祷告要么在开始时进行,要么在结束前进行,很符合2 - SAT 的条件。具体建图请看程序,不再敖述。
Ps:此题的关键在于如何判断区间是否重叠,请大家注意。
请看程序:
#include <iostream> #include <set> #include <algorithm> #include <map> #include <cstdio> #include <cstdlib> #include <stack> #include <cstring> #include <map> #include <vector> #include <string> #include <queue> #include <cmath> #define eps 1e-7 #define mem(a , b) memset(a , b , sizeof(a) ) using namespace std ; const int MAXN = 1e5 + 5 ; struct Node { int st ; int e ; }s[MAXN * 2] ; int stap[MAXN * 2] ; int c ; int n ; bool mark[MAXN * 2] ; vector<int> G[MAXN * 2] ; void chu() { int i ; for(i = 0 ; i < MAXN * 2 ; i ++) G[i].clear() ; mem(mark , 0) ; c = -1 ; } void add(int x , int y) { G[x ^ 1].push_back(y) ; G[y ^ 1].push_back(x) ; } bool dfs(int x) { if(mark[x ^ 1]) return false ; if(mark[x]) return true ; mark[x] = true ; stap[++ c] = x ; int i ; for(i = 0 ; i < G[x].size() ; i ++) { if(!dfs(G[x][i])) return false ; } return true ; } void init() { int i ; for(i = 0 ; i < n ; i ++) { int hst , mst , he , me , d ; scanf("%d:%d" , &hst , &mst) ; scanf("%d:%d" , &he , &me) ; scanf("%d" , &d) ; s[i * 2].st = hst * 60 + mst ; s[i * 2].e = hst * 60 + mst + d ; s[i * 2 + 1].st = he * 60 + me - d ; s[i * 2 + 1].e = he * 60 + me ; } } void build_G() { int i , j ; for(i = 0 ; i < 2 * n ; i ++) { for(j = i + 1 ; j < 2 * n ; j ++) { if((j ^ 1) == i) continue ; // 此处关键是如何判断区间是否重叠 !!! if((s[i].st <= s[j].st && s[i].e > s[j].st) || (s[i].st < s[j].e && s[i].e >= s[j].e)) { add(i ^ 1 , j ^ 1) ; } else if((s[j].st <= s[i].st && s[j].e > s[i].st) || (s[j].st < s[i].e && s[j].e >= s[i].e)) { add(i ^ 1 , j ^ 1) ; } } } } bool pan() { int i ; for(i = 0 ; i < n ; i ++) { if(!mark[i * 2] && !mark[2 * i + 1]) { c = -1 ; // 注意此处 ,勿忘记 !! if(!dfs(i * 2)) { while (c >= 0) { int tmp = stap[c --] ; mark[tmp] = false ; } if(!dfs(i * 2 + 1)) { return false ; } } } } return true ; } void solve() { build_G() ; if(pan()) { puts("YES") ; int i ; for(i = 0 ; i < 2 * n ; i ++) { if(mark[i]) printf("%02d:%02d %02d:%02d\n" , s[i].st / 60 , s[i].st % 60 , s[i].e / 60 , s[i].e % 60) ; } } else { puts("NO") ; } } int main() { while (scanf("%d" , &n) != EOF) { chu() ; init() ; solve() ; } return 0 ; }