1 #include "cstdio"  2 #include "vector"  3 #include "stack"  4 #include "cstring"  5 using namespace std;  6 #define maxn 2010  7   8 int n,N,dfs_clock,scc_cnt,v,tt=0;  9 char st[10]; 10 int S[maxn],T[maxn],D[maxn],pre[maxn],sccno[maxn],lowlink[maxn],id[maxn],cfl[maxn],color[maxn],done[maxn]; 11 int G[maxn][maxn],G2[maxn][maxn]; 12 stack<int> St; 13  14 void tarjan(int u) 15 { 16     pre[u]=lowlink[u]=++dfs_clock; 17     St.push(u); 18     for (int i=1;i<=G[u][0];i++) 19     { 20         int v=G[u][i]; 21         if (!pre[v]) 22         { 23             tarjan(v); 24             lowlink[u]=min(lowlink[u],lowlink[v]); 25         } 26         else if (!sccno[v]) 27         { 28             lowlink[u]=min(lowlink[u],pre[v]); 29         } 30     } 31     if (lowlink[u]==pre[u]) 32     { 33         scc_cnt++; 34         for (;;) 35         { 36             int x=St.top(); 37             St.pop(); 38             sccno[x]=scc_cnt; 39             if (x==u) break; 40         } 41     } 42 } 43  44 void find_scc(int n) 45 { 46     dfs_clock=scc_cnt=0; 47     memset(sccno,0,sizeof(sccno)); 48     memset(pre,0,sizeof(pre)); 49     for (int i=1;i<=n;i++) 50         if (!pre[i]) 51             tarjan(i); 52 } 53  54 void add_edge(int x,int y) 55 { 56     G[x][0]++; 57     G[x][G[x][0]]=y; 58 } 59  60 void _add_edge(int x,int y) 61 { 62     G2[x][0]++; 63     G2[x][G2[x][0]]=y; 64 } 65  66 void solve() 67 { 68     //1->N:x[i]        N+1->2N:not x[i] 69     v=N*2; 70     for (int i=1;i<=N;i++) 71     { 72         for (int j=i+1;j<=N;j++) 73         { 74             if (min(S[i]+D[i],S[j]+D[j])>max(S[i],S[j]))    //事件i和j不能同时满足，连边 75             { 76                 add_edge(i,N+j); 77                 add_edge(j,N+i); 78             } 79             if (min(S[i]+D[i],T[j])>max(S[i],T[j]-D[j])) 80             { 81                 add_edge(i,j); 82                 add_edge(N+j,N+i); 83             } 84             if (min(T[i],S[j]+D[j])>max(T[i]-D[i],S[j])) 85             { 86                 add_edge(N+i,N+j); 87                 add_edge(j,i); 88             } 89             if (min(T[i],T[j])>max(T[i]-D[i],T[j]-D[j])) 90             { 91                 add_edge(N+i,j); 92                 add_edge(N+j,i); 93             } 94         } 95     } 96 } 97  98 void topsort(int x) 99 {100     int j;101     id[x] = -1;102     done[++tt]=x;103     for(int k=1;k<=G2[x][0];k++)104     {105         j = G2[x][k];106         id[j]--;107         if( id[j] == 0 ) topsort( j );108     }109 }110 111 void dfs( int i )112 {113     int j;114     color[i] = 2;115     for(int k=1;k<=G[i][0];k++)116     {117         j = G2[i][k];118         if( color[j] == 0 ) dfs( j );119     }120 }121 122 void print( int aa, int bb )123 {124     if( aa / 60 < 10 ) printf( "0" );125     printf( "%d:", aa / 60 );126     if( aa % 60 < 10 ) printf( "0" );127     printf( "%d ", aa % 60 );128     if( bb / 60 < 10 ) printf( "0" );129     printf( "%d:", bb / 60 );130     if( bb % 60 < 10 ) printf( "0" );131     printf( "%d\n", bb % 60 );132 }133 134 int main()135 {136     scanf("%d",&N);137     for( int i = 1; i <= N; i++ )       //时间统一转化成分钟存储138     {139         scanf( "%s", st );140         S[i] = ( st[0]-48 )*600 + ( st[1]-48 )*60;141         S[i] += ( st[3]-48 )*10 + st[4]-48;142         scanf( "%s", st );143         T[i] = ( st[0]-48 )*600 + ( st[1]-48 )*60;144         T[i] += ( st[3]-48 )*10 + st[4]-48;145         scanf( "%d", &D[i] );146     }147 148     solve();149     find_scc(2*N);150 151     for (int i=1;i<=N;i++)152     {153         if (sccno[i]==sccno[N+i])154         {155             printf("NO\n");156             return 0;157         }158     }159 160     //printf("YES\n");161     for (int i=1;i<=2*N;i++)        //强连通分量缩点并反向连边162     {163         for (int j=1;j<=G[i][0];j++)164         {165             int tm=G[i][j];166             if (sccno[i]!=sccno[tm])167             {168                 _add_edge(sccno[tm],sccno[i]);169                 id[sccno[i]]++;170             }171         }172     }173     for (int i=1;i<=scc_cnt;i++)    //对缩点之后的块拓扑排序，174         if (id[i]==0)175             topsort(i);176 177     for( int i = 1; i <= N; i++ )178     {179         cfl[ sccno[i] ] = sccno[i+N];180         cfl[ sccno[i+N] ] = sccno[i];181     }182     for( int ii = 1; ii <= scc_cnt; ii++ )183     {184         int i = done[ii];185         if( color[i] != 0 ) continue;186         color[i] = 1;187         dfs( cfl[i] );188     }189     printf("YES\n");190     for( int i = 1; i <= N; i++ )191         if( color[ sccno[i] ] == 1 )192             print( S[i], S[i]+D[i] );193         else194             print( T[i]-D[i], T[i] );195 196     return 0;197 }198 199 200 //一直觉得ICPC不应该是种功利性的东西，那样就彻底变味了，也没意义了201 //今年要干就好好干吧，也许明年就不打了202 //没办法，有些事太复杂203 //反正个人认为几个真心的朋友比所谓的成绩重要得多得多。204 //。205 //就这样吧