题解：牧师约翰最忙碌的一天

一、题目分析

本题中牧师约翰在9月1日要为(N)对情侣主持婚礼，每对情侣婚礼有开始时间(S_i)和结束时间(T_i)，且有一个必须的仪式，该仪式可以在婚礼开始后的(D_i)分钟内进行，也可以在婚礼结束前的(D_i)分钟内进行。要求判断是否能为每对情侣安排仪式时间，使所有仪式时间不重叠，若可以则给出一种安排方案。

二、解题思路

本题可转化为2-SAT问题，利用Tarjan算法求强连通分量来解决。

（一）变量与图的构建

• 对于每对情侣(i)，设两个布尔变量：
  • 变量(x_i)表示仪式在婚礼开始后的(D_i)分钟内进行（即时间段(S_i\sim S_i + D_i)）。
  • 变量(\neg x_i)表示仪式在婚礼结束前的(D_i)分钟内进行（即时间段(T_i - D_i\sim T_i)）。
• 构建有向图：
  • 遍历每两对情侣(i)和(j)（(j < i)），判断他们可选的仪式时间段是否重叠。若重叠，则在图中添加有向边：
    • 若情侣(i)的开始时间段和情侣(j)的开始时间段重叠，添加边((i, j + n))和((j, i + n))，表示若(i)选开始时间段则(j)必须选结束时间段，反之亦然。
    • 若情侣(i)的开始时间段和情侣(j)的结束时间段重叠，添加边((i, j))和((j + n, i + n))。
    • 若情侣(i)的结束时间段和情侣(j)的开始时间段重叠，添加边((i + n, j + n))和((j, i))。
    • 若情侣(i)的结束时间段和情侣(j)的结束时间段重叠，添加边((i + n, j))和((j + n, i))。

（二）Tarjan算法求强连通分量

使用Tarjan算法对构建好的有向图进行处理，找到图中的强连通分量。Tarjan算法的具体过程如下：
1. 初始化：定义时间戳(ts)记录节点访问顺序，栈(stk)存储正在访问的节点，数组(dfn)记录节点首次访问时间，(low)记录节点及其子树能追溯到的最早首次访问时间。
2. 深度优先搜索：从每个未访问的节点(u)开始深度优先搜索。
- 访问节点(u)时，初始化(dfn[u]=low[u]=++ts)，将(u)入栈并标记在栈中。
- 遍历(u)的出边，对于边指向的节点(j)：
- 若(j)未访问，递归调用(tarjan(j))，并更新(low[u] = min(low[u], low[j]))。
- 若(j)在栈中，更新(low[u] = min(low[u], dfn[j]))。
3. 确定强连通分量：当(low[u] = dfn[u])时，说明找到一个强连通分量，不断从栈中弹出节点，直到弹出(u)，并给这些节点标记相同的强连通分量编号。

（三）判断是否有解及输出方案

• 判断是否有解：对于每对情侣(i)，若(x_i)和(\neg x_i)（即节点(i)和(i + n)）在同一个强连通分量中，则无解。因为这意味着这对情侣的两种仪式选择方式互相矛盾，不能同时成立。
• 输出方案：若有解，对于每对情侣(i)，比较节点(i)和(i + n)所在强连通分量的编号。若(id[i] < id[i + n])，则选择在婚礼开始后的(D_i)分钟内进行仪式；否则选择在婚礼结束前的(D_i)分钟内进行仪式，并按要求格式输出时间。

三、代码实现细节

（一）头文件与全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, M = 4000010;

int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts, stk[N], top;
int id[N], cnt;
bool ins[N];

struct Wedding
{
    int s, t, d;
}w[N];

• 引入输入输出、字符串操作、算法相关头文件。
• 定义常量(N)和(M)表示节点数和边数上限。
• 定义变量(n)表示情侣对数，以及邻接表相关数组(h)、(e)、(ne)、(idx)。
• 定义Tarjan算法相关数组(dfn)、(low)、(ts)、(stk)、(top)、(id)、(cnt)和标记数组(ins)。
• 定义结构体(Wedding)存储每对情侣婚礼的开始时间(s)、结束时间(t)和仪式所需时间(d)。

（二）判断时间段重叠函数is_overlap

bool is_overlap(int a, int b, int c, int d)
{
    return d > a && b > c;
}

该函数用于判断两个时间段([a, b])和([c, d])是否重叠，若重叠返回true，否则返回false。

（三）添加边函数add

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

用于向邻接表中添加一条从节点(a)到节点(b)的有向边。

（四）Tarjan算法函数tarjan

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[ ++ top] = u, ins[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (ins[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u])
    {
        int y;
        cnt ++ ;
        do
        {
            y = stk[top -- ], ins[y] = false, id[y] = cnt;
        }while (y != u);
    }
}

• 开始时初始化(dfn[u])和(low[u])，将(u)入栈并标记在栈中。
• 遍历(u)的出边，根据节点(j)的访问情况更新(low[u])。
• 当(low[u] = dfn[u])时，弹出栈中节点并标记它们属于同一个强连通分量。

（五）main函数

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n; i ++ )
    {
        int s0, s1, t0, t1, d;
        scanf("%d:%d %d:%d %d", &s0, &s1, &t0, &t1, &d);
        w[i] = {s0 * 60 + s1, t0 * 60 + t1, d};
    }

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < i; j ++ )
        {
            auto a = w[i], b = w[j];
            if (is_overlap(a.s, a.s + a.d, b.s, b.s + b.d)) add(i, j + n), add(j, i + n);
            if (is_overlap(a.s, a.s + a.d, b.t - b.d, b.t)) add(i, j), add(j + n, i + n);
            if (is_overlap(a.t - a.d, a.t, b.s, b.s + b.d)) add(i + n, j + n), add(j, i);
            if (is_overlap(a.t - a.d, a.t, b.t - b.d, b.t)) add(i + n, j), add(j + n, i);
        }

    for (int i = 0; i < n * 2; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 0; i < n; i ++ )
        if (id[i] == id[i + n])
        {
            puts("NO");
            return 0;
        }

    puts("YES");
    for (int i = 0; i < n; i ++ )
    {
        auto a = w[i];
        int s = a.s, t = a.t, d = a.d;
        if (id[i] < id[i + n])
            printf("%02d:%02d %02d:%02d\n", s / 60, s % 60, (s + d) / 60, (s + d) % 60);
        else
            printf("%02d:%02d %02d:%02d\n", (t - d) / 60, (t - d) % 60, t / 60, t % 60);
    }

    return 0;
}

• 读取情侣对数(n)，初始化邻接表。
• 读取每对情侣婚礼的时间信息，存储到结构体数组(w)中。
• 遍历每两对情侣，判断时间段是否重叠，若重叠则在图中添加相应有向边。
• 对每个未访问的节点调用Tarjan算法，求出强连通分量。
• 检查每对情侣对应的两个节点是否在同一个强连通分量中，判断是否有解。
• 若有解，根据节点所在强连通分量编号输出每对情侣仪式的时间安排。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 建图阶段：两层循环遍历每两对情侣判断时间段重叠并建边，时间复杂度为(O(n^2))。
• Tarjan算法阶段：对图中的每个节点和边进行一次访问，图中节点数为(2n)，边数最多为(O(n^2))，时间复杂度为(O(2n + n^2)=O(n^2))。
• 因此，总的时间复杂度为(O(n^2))。

（二）空间复杂度

• 邻接表存储图的边信息，最多有(O(n^2))条边，空间复杂度为(O(n^2))。
• 其他辅助数组如(dfn)、(low)、(id)等，大小为(2n)，空间复杂度为(O(n))。
• 所以，总的空间复杂度为(O(n^2))。