牧师约翰最忙碌的一天

C++ 代码

/*
如果我们将每场婚礼看作是一个变量，那么每个变量就会有 开始时举办仪式 和 结束时举办仪式 两种取值，
那么就启发我们可以用 2-SAT 来求解。将两种取值分别记为 x[i][0] 和 x[i][1]，并看作节点 i 和 i + N

枚举每两场婚礼 i, j，若婚礼 i 的 x[i][p] 时间段与婚礼 j 的 x[j][q] 时间段重叠，则说明两者不能同时
被选为最终赋值。转化成 2-SAT 的形式，应该连 (i + p * N, j + (1 - q) * N) 和 (j + q * N, i + (1 - p) * N)
两条有向边，两者互为逆否命题。

用 Tarjan 算法求强联通分量，检查是否存在 i 和 i + N 在同一个强连通分量即可。本题还需要输出方案。

这里给出 2-SAT 合法方案的两种构造方法。

第一种构造方法

首先，在一个强连通分量中，只要确定了一个变量的赋值，该强连通分量内其他变量的赋值也就直接确定了，
这启发我们考虑缩点，其次，因为互为逆否命题的有向边在图中成对出现，所以一个零出度点对面的点一定有出边。
选择一个有出边的店会使得该边指向的点必须也被选择，而选择一个零出度点则不会对其他任何点造出影响。

根据上述讨论，第一种构造方法的基本思想就是：自底向上执行拓扑排序，不断尝试选择零出度点。

1. 把强连通分量缩点，因为一般的拓扑排序是自顶向下根据入度进行的，所以我们建立一张缩点后的反图，具体来说：
    (1) 图上每个点都对应原图的强连通分量
    (2) 原图中的边 (x, y) 转化为新图中的边 (c[y], c[x])，其中 c[x] != c[y]，c[x] 表示节点 x 所在的强连通分量
    (3) 对于原图中每个点 x，c[x] 和 c[x + N] 新图中两个对称的节点。
2. 在上述反图上统计每个点的入度，执行拓扑排序

    设val[k] 表示原图 k 号强连通分量的赋值标记，初始值为 -1

    从队头每取出一个节点 k (k 相当于原图中一个强连通分量的编号)，就检查 k 的赋值标记，若 val[k] = -1 (尚未确定赋值)，
    就令 val[k] = 0， val[k + N] = 1，随后把它能到达的点的入度减 1 (拓扑排序的正常过程)

3. 拓扑排序结束之后，就得到最终的答案，对于原图每个节点 i：
    若 val[c[i]] = 0，则变量 x[i] 应赋值为 x[i][0]
    若 val[c[i]] = 1，则变量 x[i] 应赋值为 x[i][1]

第二种构造方法

第二种构造方法是基于第一种构造方法的基础上，进一步利用了 Tarjan 算法对强连通分量编号的特殊性质，使得构造过程更简洁。
可以发现 Tarjan 算法的本质是一次 dfs，它在回溯时会先取出有向图底部的强连通分量进行标记，所以 Tarjan 算法得到的强连
通分量编号本身就已经满足缩点后有向无环图中自底向上的顺序，序列 1, 2, ..., cnt 就是缩点后的反图的拓扑序，无需进行拓
扑排序。

因此，直接比较节点所在的强连通分量的编号大小，即可确定对应变量的赋值 val[i]，c[i] 和 c[i + N] 哪个小，就表示哪个会
先被遍历到，先被遍历到的是取值为 0，后被遍历到的取值为 1。

最终，同样的枚举一遍所有节点，根据 val[i] 来确定每个节点的值。

注：构造方法2 其实等于是 构造方法1 的升级版
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2010, M = 4000010;

int n;
int h[N], e[M], ne[M], idx; //邻接表
int dfn[N], low[N], timestamp; //时间戳、能到达的最小时间戳，用到的时间戳
int id[N], scc_cnt; //每个节点所在的scc编号、当前scc数量
int stk[N], top; //栈
bool in_stk[N]; //每个点是否在栈中
int s[N], t[N], d[N]; //每场婚礼的开始时间、结束时间、需要的仪式时间
int opp[N]; //每个编号对应的另一个编号，例：opp[i] = i + n, opp[i + n] = i
int val[N]; //每场婚礼选取的仪式时间(1 表示开始时举行仪式，0 表示结束时举行仪式)

void add(int a, int b) //添加边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//判断时间段 a~b 和 c~d 是否重叠
bool check(int a, int b, int c, int d)
{
    //三种重叠情况：c--a--d--b 、 a--c--b--d 、 a--c--d--b
    if((a >= c && a < d) || (b > c && b <= d) || (a <= c && b >= d)) return true; //重叠
    return false; //不重叠
}

void tarjan(int u) //Tarjan 求强连通分量(模板)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];

        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
        } while(y != u);
    }
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int sh, sm, th, tm;
        scanf("%d:%d %d:%d %d", &sh, &sm, &th, &tm, &d[i]);
        s[i] = sh * 60 + sm, t[i] = th * 60 + tm; //计算每场婚礼的开始时间、结束时间(以秒为单位)
    }

    //建图
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
        {
            if(check(s[i], s[i] + d[i], s[j], s[j] + d[j])) // i头 和 j头 重叠
                add(i, j + n), add(j, i + n); // i头 -> j尾   j头 -> i尾
            if(check(s[i], s[i] + d[i], t[j] - d[j], t[j])) // i头 和 j尾 重叠
                add(i, j), add(j + n, i + n); // i头 -> j头   j尾 -> i尾
            if(check(t[i] - d[i], t[i], s[j], s[j] + d[j])) // i尾 和 j头 重叠
                add(i + n, j + n), add(j, i); // i尾 -> j尾   j头 -> i头
            if(check(t[i] - d[i], t[i], t[j] - d[j], t[j])) // i尾 和 j尾 重叠
                add(i + n, j), add(j + n, i); // i尾 -> j头   j尾 -> i头
        }

    //求出所有强连通分量
    for(int i = 1; i <= 2 * n; i++)
        if(!dfn[i])
            tarjan(i);

    //判断是否有解
    for(int i = 1; i <= n; i++)
    {
        if(id[i] == id[i + n]) //如果存在某个点的两个取值在同一个连通分量中
        {
            puts("NO"); //无解
            return 0; //直接结束
        }
        opp[i] = i + n, opp[i + n] = i; //否则说明有解，记录一下对应关系
    }

    puts("YES"); //到这说明有解，需要输出合法方案

    //枚举每场婚礼，并确定它的取值
    for(int i = 1; i <= 2 * n; i++) val[i] = id[i] > id[opp[i]]; //编号小的取值为 0，编号大的取值为 1

    //输出所有婚礼的仪式时间
    for(int i = 1; i <= n; i++)
        if(!val[i]) //取值为 0，开头举行仪式
            printf("%02d:%02d %02d:%02d\n", s[i] / 60, s[i] % 60, (s[i] + d[i]) / 60, (s[i] + d[i]) % 60);
        else //取值为 1，结尾举行仪式
            printf("%02d:%02d %02d:%02d\n", (t[i] - d[i]) / 60, (t[i] - d[i]) % 60, t[i] / 60, t[i] % 60);

    return 0;
}