牧师约翰在 9 月 1 日这天非常的忙碌。



有 N 对情侣在这天准备结婚，每对情侣都预先计划好了婚礼举办的时间，其中第 i 对情侣的婚礼从时刻 Si 开始，到时刻 Ti 结束。



婚礼有一个必须的仪式：站在牧师面前聆听上帝的祝福。



这个仪式要么在婚礼开始时举行，要么在结束时举行。



第 i 对情侣需要 Di 分钟完成这个仪式，即必须选择 Si∼Si+Di 或 Ti−Di∼Ti 两个时间段之一。



牧师想知道他能否满足每场婚礼的要求，即给每对情侣安排Si∼Si+Di 或 Ti−Di∼Ti，使得这些仪式的时间段不重叠。



若能满足，还需要帮牧师求出任意一种具体方案。



注意，约翰不能同时主持两场婚礼，且 所有婚礼的仪式均发生在 9 月 1 日当天。



如果一场仪式的结束时间与另一场仪式的开始时间相同，则不算重叠。



例如：一场仪式安排在 08:00∼09:00，另一场仪式安排在 09:00∼10:00，则不认为两场仪式出现重叠。



输入格式

第一行包含整数 N。



接下来 N 行，每行包含 Si,Ti,Di，其中 Si 和 Ti 是 hh:mm 形式。



输出格式

第一行输出能否满足，能则输出 YES，否则输出 NO。



接下来 N 行，每行给出一个具体时间段安排。



数据范围

1≤N≤1000

输入样例：

2

08:00 09:00 30

08:15 09:00 20

输出样例：

YES

08:00 08:30

08:40 09:00

题解
2-SAT问题

#include

using namespace std;

const int N = 2e3 + 10;

const int M = 4e6 + 10;

int low[N],num[N],dfn;

int sta[N],in_sta[N],top;

int scc[N],sccno;

int head[N],cnt;

struct Edge{ 

   

    int v,next;

}edge[M];

void add(int u,int v){ 

   

    edge[cnt].v = v;

    edge[cnt].next = head[u];

    head[u] = cnt ++;

}

void Tarjan(int u){ 

   

    low[u] = num[u] = ++ dfn;

    sta[top ++] = u,in_sta[u] = true;

    for(int i = head[u];~i;i = edge[i].next){ 

   

        int v = edge[i].v;

        if(!num[v]){ 

   

            Tarjan(v);

            low[u] = min(low[u],low[v]);

        }

        else if(in_sta[v])low[u] = min(low[u],num[v]);

    }

    if(low[u] == num[u]){ 

   

        sccno ++;

        while(true){ 

   

            int t = sta[-- top];

            in_sta[t] = false;

            scc[t] = sccno;

            if(t == u)break;

        }

    }

}

bool check(int a,int b,int c,int d){ 

   

    return !(c >= b || d <= a);

}

struct node{ 

   

    int b1,e1,b2,e2;

}Node[N],Node1[N];

int get(int a,int b){ 

   

    return a * 60 + b;

}

bool cmp1(const node &a,const node &b){ 

   

    return a.b1 < b.b1;

}

int main(){ 

   

    int n;

    memset(head,-1,sizeof head);

    cin>>n;

    int x1,y1,x2,y2,d;

    for(int i = 0;i < n;i ++){ 

   

        scanf("%d:%d %d:%d %d",&x1,&y1,&x2,&y2,&d);

        Node[i].b1 = get(x1,y1),Node[i].e1 = get(x1,y1) + d;

        Node[i].b2 = get(x2,y2) - d,Node[i].e2 = get(x2,y2);

    }

    for(int i = 0;i < n;i ++){ 

   

        for(int j = 0;j < n;j ++){ 

   

            if(i == j)continue;

            bool a = check(Node[i].b1,Node[i].e1,Node[j].b1,Node[j].e1);

            bool b = check(Node[i].b1,Node[i].e1,Node[j].b2,Node[j].e2);

            bool c = check(Node[i].b2,Node[i].e2,Node[j].b1,Node[j].e1);

            bool d = check(Node[i].b2,Node[i].e2,Node[j].b2,Node[j].e2);

            if(a ){ 

   

                add(i * 2,j * 2 + 1);

            }

            if(b){ 

   

                add(i * 2,j * 2);

            }

            if(c ){ 

   

                add(i * 2 + 1,j * 2 + 1);

            }

            if(d){ 

   

                add(i * 2 + 1,j * 2);

            }

        }

    }

    for(int i = 0;i < 2 * n;i ++){ 

   

        if(!num[i])Tarjan(i);

    }

    for(int i = 0;i < n;i ++){ 

   

        if(scc[2 * i] == scc[2 * i + 1]){ 

   

            cout<<"NO"<
            return 0;

        }

    }

    cout<<"YES"<
    for(int i = 0;i < n;i ++){ 

   

        if(scc[2 * i] < scc[2 * i + 1]){ 

   

            printf("%02d:%02d %02d:%02d\n",Node[i].b1 / 60,Node[i].b1 % 60,Node[i].e1 / 60,Node[i].e1 % 60);

        }else printf("%02d:%02d %02d:%02d\n",Node[i].b2 / 60,Node[i].b2 % 60,Node[i].e2 / 60,Node[i].e2 % 60);

    }

    return 0;

}