题意方法和之前的3648基本一样
注意输出解的方式，分成两部分的点集，应该遍历其中一个点集，根据染色判断选择该点集的点还是另一个点集的点
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define MAXN 5005
#define MAXM 50005
#define INF 1000000000
using namespace std;
int start[MAXN], end[MAXN], last[MAXN];
int n, index, scc;
vector<int>g[MAXN], dag[MAXN];
int dfn[MAXN], low[MAXN], instack[MAXN];
int fa[MAXN], ha[MAXN], color[MAXN], ind[MAXN];
queue<int>q;
stack<int>st;
void init()
{index = scc = 0;memset(instack, 0, sizeof(instack));for(int i = 0; i < MAXN; i++) g[i].clear(), dag[i].clear();memset(dfn, 0, sizeof(dfn));memset(color, 0, sizeof(color));memset(ind, 0, sizeof(ind));memset(ha, 0, sizeof(ha));while(!q.empty()) q.pop();while(!st.empty()) st.pop();
}
bool conflict(int lx, int ly, int rx, int ry)
{if(lx >= rx && lx <= ry) return true;if(ly >= rx && ly <= ry) return true;if(rx >= lx && rx <= ly) return true;if(ry >= lx && ry <= ly) return true;return false;
}
void build()
{for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++){if(conflict(start[i], start[i] + last[i] - 1, start[j], start[j] + last[j] - 1)) g[i].push_back(j + n), g[j].push_back(i + n);if(conflict(start[i], start[i] + last[i] - 1, end[j] - last[j] , end[j] - 1)) g[i].push_back(j), g[j + n].push_back(i + n);if(conflict(end[i] - last[i], end[i] - 1, start[j], start[j] + last[j] - 1)) g[i + n].push_back(j + n), g[j].push_back(i);if(conflict(end[i] - last[i], end[i] - 1, end[j] - last[j] , end[j] - 1)) g[i + n].push_back(j), g[j + n].push_back(i);}
}
void tarjan(int u)
{dfn[u] = low[u] = ++index;int size = g[u].size();int v;instack[u] = 1;st.push(u);for(int i = 0; i < size; i++){v = g[u][i];if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else if(instack[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){scc++;do{v = st.top();st.pop();instack[v] = 0;fa[v] = scc;}while(v != u);}
}
void buildDag()
{for(int u = 1; u <= 2 * n; u++){int size = g[u].size();for(int i = 0; i < size; i++){int v = g[u][i];if(fa[u] != fa[v]) dag[fa[v]].push_back(fa[u]), ind[fa[u]]++;}}
}
void topsort()
{for(int i = 1; i <= scc; i++)if(ind[i] == 0) q.push(i);while(!q.empty()){int u = q.front();q.pop();if(!color[u]) color[u] = 1, color[ha[u]] = 2;int size = dag[u].size();for(int i = 0; i < size; i++){int v = dag[u][i];ind[v]--;if(ind[v] == 0) q.push(v);}}
}
void solve()
{for(int i = 1; i <= 2 * n; i++)if(!dfn[i]) tarjan(i);for(int i = 1; i <= n; i++)if(fa[i] == fa[i + n]){puts("NO");return;}else ha[fa[i]] = fa[i + n], ha[fa[i + n]] = fa[i];buildDag();topsort();printf("YES\n");for(int i = 1; i <= n; i++)if(color[fa[i]] == 1){int h1, h2, m1, m2;h1 = start[i] / 60;h2 = (start[i] + last[i]) / 60;m1 = start[i] % 60;m2 = (start[i] + last[i]) % 60;printf("%02d:%02d %02d:%02d\n", h1, m1, h2, m2);}else{int h1, h2, m1, m2;h1 = (end[i] - last[i]) / 60;h2 = end[i] / 60;m1 = (end[i] - last[i]) % 60;m2 = end[i] % 60;printf("%02d:%02d %02d:%02d\n", h1, m1, h2, m2);}
}
int main()
{int hour, miniute;while(scanf("%d", &n) != EOF){init();for(int i = 1; i <= n; i++){scanf("%d:%d", &hour, &miniute);start[i] = hour * 60 + miniute;scanf("%d:%d", &hour, &miniute);end[i] = hour * 60 + miniute;scanf("%d", &last[i]);}build();solve();}return 0;
}