具体看注释

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=2010,M=4e6+10;//要开2倍，否则RE

struct Node{
    int s,t,d;
}k[N];

bool ins[N];
int n,low[N],dfn[N],h[N],ne[M],e[M],tot,bel[N],cnt,idx;
int st[N],top=0;

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

void Tarjan(int x)
{
    st[++top]=x;
    low[x]=dfn[x]=++tot;ins[x]=1;

    for (int i=h[x];~i;i=ne[i])
        if (!dfn[e[i]])
        {
            Tarjan(e[i]);
            low[x]=min(low[x],low[e[i]]);
        }
        else if (ins[e[i]]) low[x]=min(low[x],dfn[e[i]]);

    if (dfn[x]!=low[x]) return ;
    ++cnt;int now;
    do{
        now=st[top--];
        ins[now]=0;
        bel[now]=cnt;
    }while (now!=x);
    return;
}//Tarjan模板

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

int main()
{
    memset(h,-1,sizeof h);
    memset(dfn,0,sizeof (dfn));
    cin>>n;
    for (int i=1,h1,t1,h2,t2;i<=n;++i)
    {
        scanf("%d:%d %d:%d %d",&h1,&t1,&h2,&t2,&k[i].d);
        k[i].s=h1*60+t1;
        k[i].t=h2*60+t2;
    }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        {
            if (i==j) continue;
            int s1=k[i].s,s2=k[j].s,t1=k[i].t,t2=k[j].t,d1=k[i].d,d2=k[j].d;
            if (check(s1,s1+d1,s2,s2+d2)) add(i,j+n),add(j,i+n);
            if (check(s1,s1+d1,t2-d2,t2)) add(i,j),add(j+n,i+n);
            if (check(t1-d1,t1,s2,s2+d2)) add(i+n,j+n),add(j,i);
            if (check(t1-d1,t1,t2-d2,t2)) add(i+n,j),add(j+n,i);//2-SAT模板
        }
    for (int i=1;i<=2*n;++i)
        if (!dfn[i]) Tarjan(i);
    for (int i=1;i<=n;++i)
        if (bel[i]==bel[n+i])
        {
            puts("NO");
            return 0;
        }
    puts("YES");
    for (int i=1;i<=n;++i)
        if (bel[i]<bel[n+i])
        {//要对齐输出
            printf("%02d:%02d %02d:%02d\n",k[i].s/60,k[i].s%60,(k[i].s+k[i].d)/60,(k[i].s+k[i].d)%60);
        }
        else
        {
            printf("%02d:%02d %02d:%02d\n",(k[i].t-k[i].d)/60,(k[i].t-k[i].d)%60,k[i].t/60,k[i].t%60);
        }//输出
    return 0;
}