题目地址：POJ：3683 — Priest John’s Busiest Day

题目描述

John is the only priest in his town. September 1st is the John’s busiest day in a year because there is an old legend in the town that the couple who get married on that day will be forever blessed by the God of Love. This year N couples plan to get married on the blessed day. The i-th couple plan to hold their wedding from time Si to time Ti. According to the traditions in the town, there must be a special ceremony on which the couple stand before the priest and accept blessings. The i-th couple need Di minutes to finish this ceremony. Moreover, this ceremony must be either at the beginning or the ending of the wedding (i.e. it must be either from Si to Si + Di, or from Ti – Di to Ti). Could you tell John how to arrange his schedule so that he can present at every special ceremonies of the weddings.
Note that John can not be present at two weddings simultaneously.
每个婚礼各有两段时间可以选择，要求每对新人的婚礼的时间不能重叠，求可行方案。

输入输出格式

输入格式：
The first line contains a integer N ( 1 ≤ N ≤ 1000).
The next N lines contain the Si, Ti and Di. Si and Ti are in the format of hh:mm.

输出格式：
The first line of output contains “YES” or “NO” indicating whether John can be present at every special ceremony. If it is “YES”, output another N lines describing the staring time and finishing time of all the ceremonies.

输入输出样例

输入样例#1：

2
08:00 09:00 30
08:15 09:00 20

输出样例#1：

YES
08:00 08:30
08:40 09:00

题解

本题同样是比较裸的2-SAT题目，只是利用本题来讲解2-SAT算法的优化如何实现。下面的内容也参考了《2-SAT算法浅析》（华师一附中 赵爽）的内容。
首先是建图的部分，我们对于任意一对可能冲突的时间段分别建边即可。剩下的事情就是跑一遍2-SAT。
我们知道，2-SAT图中的有向边表示的是一种“必须选择”的关系，那么如果图中有一个强连通分量，这个SCC中只要选中了就比如选里面所有的点。那么原来看上去很大的图就可以直接缩点成一个比较小的图，我们再考虑在小图上的工作。注意，缩点后的图中，SCC间的边要反向，原因将会在之后提到。
首先，如果有对立点存在于同一个SCC中，那么无解。
接着我们考虑利用这个有向无环图的拓扑序获得答案。我们先选中一个拓扑序列中未标记的点，然后DFS处理这个点的对立点所在的SCC。既然对立点所在SCC不能被选中，那么要求必须选中它的点就也不会选中，所以在原图的边的反向上，DFS应当沿着入边一路处理到入度为0的点，这里建反边的优势就体现出来了。重复这一工作，直到所有点都有一个标记“选中”或“不选”。
接着按照所在SCC的标记来输出可行解即可。

代码

以下代码借鉴了「POJ3683」Priest John’s Busiest Day – 2-SAT – hzwer.com的写法，感谢hzwer学长。

// Code by KSkun, 2018/3
#include <cstdio>

#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 2005;

std::vector<int> gra[MAXN], gra2[MAXN];
int n, begin[MAXN], end[MAXN], mark[MAXN], deg[MAXN];
int dfn[MAXN], low[MAXN], tot, scc, belong[MAXN], op[MAXN];
std::stack<int> sta;
std::queue<int> que;
bool insta[MAXN];

inline bool notconflict(int x, int y) {
    return begin[x] >= end[y] || begin[y] >= end[x];
}

inline void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    sta.push(u); insta[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        int t = 0; scc++;
        while(t != u) {
            t = sta.top(); sta.pop();
            insta[t] = false;
            belong[t] = scc;
        }
    }
}

inline void dfs(int u) {
    if(mark[u]) return;
    mark[u] = -1;
    for(int i = 0; i < gra2[u].size(); i++) {
        int v = gra2[u][i];
        dfs(v);
    }
}

inline void toposort() {
    for(int i = 1; i <= scc; i++) {
        if(!deg[i]) que.push(i);
    }
    while(!que.empty()) {
        int u = que.front(); que.pop();
        if(mark[u]) continue;
        mark[u] = 1;
        dfs(op[u]);
        for(int i = 0; i < gra2[u].size(); i++) {
            int v = gra2[u][i];
            deg[v]--;
            if(!deg[v]) que.push(v);
        }
    }
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        begin[i << 1] = readint() * 60 + readint();
        end[(i << 1) - 1] = readint() * 60 + readint();
        int last = readint();
        end[i << 1] = begin[i << 1] + last;
        begin[(i << 1) - 1] = end[(i << 1) - 1] - last;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int a1 = i << 1, a2 = (i << 1) - 1, b1 = j << 1, b2 = (j << 1) - 1;
            if(!notconflict(a1, b1)) {
                gra[a1].push_back(b2);
                gra[b1].push_back(a2);
            }
            if(!notconflict(a1, b2)) {
                gra[a1].push_back(b1);
                gra[b2].push_back(a2);
            }
            if(!notconflict(a2, b1)) {
                gra[a2].push_back(b2);
                gra[b1].push_back(a1);
            }
            if(!notconflict(a2, b2)) {
                gra[a2].push_back(b1);
                gra[b2].push_back(a1);
            }
        }
    }
    for(int i = 1; i <= n << 1; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 1; i <= n; i++) {
        if(belong[i << 1] == belong[(i << 1) - 1]) {
            puts("NO");
            return 0;
        } 
        op[belong[i << 1]] = belong[(i << 1) - 1];
        op[belong[(i << 1) - 1]] = belong[i << 1];
    }
    puts("YES");
    for(int u = 1; u <= n << 1; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(belong[u] != belong[v]) {
                gra2[belong[v]].push_back(belong[u]);
                deg[belong[u]]++;
            }
        }
    }
    toposort();
    for(int i = 1; i <= n; i++) {
        if(mark[belong[i << 1]] == 1) {
            printf("%02d:%02d %02d:%02d\n", begin[i << 1] / 60, begin[i << 1] % 60, 
                end[i << 1] / 60, end[i << 1] % 60);
        } else {
            printf("%02d:%02d %02d:%02d\n", begin[(i << 1) - 1] / 60, begin[(i << 1) - 1] % 60, 
                end[(i << 1) - 1] / 60, end[(i << 1) - 1] % 60);
        }
    }
    return 0;
}