Priest John's Busiest Day（2 - sat）

Priest John's Busiest Day

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 7783		Accepted: 2654		Special Judge

Description

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 S_i to time T_i. 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 D_i 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 S_i to S_i + D_i, or from T_i - D_i to T_i). 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.

Input

The first line contains a integer N ( 1 ≤ N ≤ 1000). 
The next N lines contain the S_i, T_i and D_i. S_i and T_i are in the format of hh:mm.

Output

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.

Sample Input

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

Sample Output

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

 

       题意：

       给出 N（1 ~ 1000），代表有 N 个时间。后给出这 N 个时间的起点和终点和消费时间 T 。每个时间点要不从起点开始计算，要不从终点 - T 开始，要求遍历所有的时间并且任意时间之间不能有重叠。若能按要求遍历所有时间，则输出YES和这些时间段，不能则输出NO。

 

       思路：

       2 - sat。找到一种确定的关系来建图，于是找到冲突关系，若 si ~ si + T 和 sj ~ sj + T 时间有冲突，且必须选 si 的话，则必须选 ej，即 si -> ej，同时逆否命题 非ej -> 非si 也成立。同理，若 si ~ si + T 和 ej - T ~ ej  有冲突的话，必须选 si 的话，则必须选 sj，即 si -> sj。如此，一共可以判断四次来建图。建图后 2 - sat，强连通后，判断同一个 i 和 n + i 是否在同一个强连通中，不是的话则找拓扑序小的输出即可（因为拓扑序是倒序的）。

 

       判断两个时间段是否重叠的方法（L1，R1，L2，R2）：

       Min（ R1，R2 ） >  Max( L1，L2 ) 则两个时间段有重叠（不包括边界），否则则不重叠。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>

using namespace std;

const int NMAX = 1005 * 2;
const int EMAX = NMAX * NMAX;

typedef struct { int sta, End, last; }node;

node no[1005];
int n, ind;
int v[EMAX], fir[NMAX], Next[EMAX];

int dfs_clock, scc_cnt;
int low[NMAX], pre[NMAX], cmp[NMAX];
stack<int> s;

void add_edge(int f, int t) {
        v[ind] = t;
        Next[ind] = fir[f];
        fir[f] = ind;
        ++ind;
}

void dfs(int u) {
        pre[u] = low[u] = ++dfs_clock;
        s.push(u);

        for (int e = fir[u]; e != -1; e = Next[e]) {
                if (!pre[ v[e] ]) {
                        dfs( v[e] );
                        low[u] = min(low[u], low[ v[e] ]);
                } else if (!cmp[ v[e] ]) {
                        low[u] = min(low[u], pre[ v[e] ]);
                }
        }

        if (pre[u] == low[u]) {
                ++scc_cnt;
                for (;;) {
                        int x = s.top(); s.pop();
                        cmp[x] = scc_cnt;
                        if (x == u) break;
                }
        }
}

void scc() {
        scc_cnt = dfs_clock = 0;
        memset(pre, 0, sizeof(pre));
        memset(cmp, 0, sizeof(cmp));

        for (int u = 1; u <= 2 * n; ++u)
                if (!pre[u]) dfs(u);
}

bool test (int f1, int t1, int f2, int t2) {
        if (f1 >= t2 || t1 <= f2) return false;
        return true;
}

int main() {

        ind = 0;
        memset(fir, -1, sizeof(fir));

        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
                char s[10], e[10];
                scanf("%s%s%d", s, e, &no[i].last);
                no[i].sta = ( (s[0] - '0') * 10 + s[1] - '0') * 60 +
                            (s[3] - '0') * 10 + s[4] - '0';
                no[i].End = ( (e[0] - '0') * 10 + e[1] - '0') * 60 +
                            (e[3] - '0') * 10 + e[4] - '0';
        }

        for (int i = 1; i < n; ++i) {
                for (int j = i + 1; j <= n; ++j) {
                        if ( test(no[i].sta, no[i].sta + no[i].last,
                                  no[j].sta, no[j].sta + no[j].last) ) {
                                add_edge(i, n + j);
                                add_edge(j, n + i);
                        }
                        if ( test(no[i].sta, no[i].sta + no[i].last,
                                  no[j].End - no[j].last, no[j].End) ) {
                                add_edge(i, j);
                                add_edge(n + j, n + i);
                        }
                        if ( test(no[i].End - no[i].last, no[i].End,
                                  no[j].sta, no[j].sta + no[j].last) ) {
                                add_edge(n + i, n + j);
                                add_edge(j, i);
                        }
                        if ( test(no[i].End - no[i].last, no[i].End,
                                  no[j].End - no[j].last, no[j].End) ) {
                                add_edge(n + i, j);
                                add_edge(n + j, i);
                        }
                }
        }

        scc();

        for (int i = 1; i <= n; ++i) {
                if (cmp[i] == cmp[n + i]) {
                        printf("NO\n");
                        return 0;
                }
        }

        printf("YES\n");
        for (int i = 1; i <= n; ++i) {
                if (cmp[i] < cmp[n + i]) {
                        printf( "%02d:%02d %02d:%02d\n", 
                                no[i].sta / 60, no[i].sta % 60,
                                (no[i].sta + no[i].last) / 60, 
                                (no[i].sta + no[i].last) % 60 );
                } else {
                        printf( "%02d:%02d %02d:%02d\n", 
                                (no[i].End - no[i].last) / 60, 
                                (no[i].End - no[i].last) % 60,
                                no[i].End / 60, no[i].End % 60 );
                }
        }

        return 0;
}