题目来源：
http://poj.org/problem?id=3683
题意：
有N对新人举行婚礼,且每次婚礼需要持续d时间,从s时间到t时间之间举行且只能选择s到s+d时间或t-d到t时间这两个完整的时间段举行.现在只有一个神父,问他有没有可能参加所有新人的婚礼(待完整段时间且任意两对新人的婚礼时间不重叠)? 输出一个可行的方案.
分析：
每对新人的婚礼时间只有两种选择,直接就可以转化为2-SAT问题.其中如果对于第i个婚礼与第j个婚礼来说:
假设i先办的时间区间为[a,b]而j后办的时间区间为[c,d],如何判断[a,b]与[c,d]是否发生了冲突呢?(边界相交不算).
只有下面两种情况下区间[s1,e1]与区间[s2,e2]才规范相交.
1. s1<e2 且 s2<e1
2. s2<e1 且 s1<e2
仔细一看上面两种情况是相同的,只要相交的两个区间的e1 e2 > s1 s2 即可保证这两个区间相交.
(仔细想想上面情况)
然后对于冲突的每对新人添加边即可.
我们把每个婚礼可能的两个时间段看做两个点 A 和 A’，显然，如果两个时间段冲突（比如 A 和 B 的时间重合），那么需要建边（A -> B' ），（B -> A‘），判断出是否存在解后，需要输出一组解，这里的方法是 赵爽 的《2-SAT 解法浅析》里面看的，有详细的证明。
代码：
#include<iostream>
#include<cstring>
#include<stack>
#include<iomanip>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;
# define ll long long
const int maxn=41000;
int op[maxn],vis[maxn],low[maxn],dfn[maxn];
int pt[maxn],stk[maxn],color[maxn],pos[maxn],deg[maxn];
vector<int>vc[maxn],vc2[maxn];
struct Time
{int be;int en;
}t[maxn];
int n,m,sig,cnt,tot,cont;
void add(int x,int y){vc[x].push_back(y);
}
void top(){memset(pt,0,sizeof(pt));queue<int>s;for(int i=1;i<=sig;i++){if(deg[i]==0) s.push(i);}while(!s.empty()){int u=s.front();if(pt[u]==0){pt[u]=1;pt[pos[u]]=2;}s.pop();for(int i=0;i<vc2[u].size();i++){int v=vc2[u][i];deg[v]--;if(deg[v]==0) s.push(v);}}cont=0;for(int i=1;i<=n;i++) {if(pt[color[i]]==1) op[cont++]=i;}
}
void tarjan(int u){vis[u]=1;dfn[u]=low[u]=cnt++;stk[++tot]=u;for(int i=0;i<vc[u].size();i++){int v=vc[u][i];if(vis[v]==0) tarjan(v);if(vis[v]==1) low[u]=min(low[u],low[v]);}if(low[u]==dfn[u]) {sig++;do{vis[stk[tot]]=-1;color[stk[tot]]=sig;}while(stk[tot--]!=u);}
}
void init(){sig=0;cnt=1;tot=-1;memset(deg,0,sizeof(deg));memset(stk,0,sizeof(stk));memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));memset(color,0,sizeof(color));for(int i=0;i<maxn;i++) {vc[i].clear();vc2[i].clear();}
}
int solve(){for(int i=1;i<=n*2;i++) {if(vis[i]==0) tarjan(i);}for(int i=1;i<=n;i++) {if(color[i]==color[i+n]) return 0;pos[color[i]]=color[i+n];pos[color[i+n]]=color[i];}for(int i=1;i<=n*2;i++){for(int j=0;j<vc[i].size();j++){int v=vc[i][j];if(color[i]!=color[v]){deg[color[i]]++;vc2[color[v]].push_back(color[i]);}}}top();return 1;
}
bool judge(int i,int j)
{if(t[i].be>=t[j].en||t[i].en<=t[j].be)return false;elsereturn true;
}
int main()
{while(scanf("%d",&n)!=EOF){init();int len[maxn];int a,b,c,d,e;for(int i=1;i<=n;i++){scanf("%d:%d %d:%d %d",&a,&b,&c,&d,&len[i]);t[i].be=a*60+b;t[i+n].en=c*60+d;t[i].en=t[i].be+len[i];t[i+n].be=t[i+n].en-len[i];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)continue;if(judge(i,j))add(i,j+n);if(judge(i,j+n))add(i,j);if(judge(i+n,j))add(i+n,j+n);if(judge(i+n,j+n))add(i+n,j);}int ans=solve();if(ans==0)printf("NO\n");else{printf("YES\n");for(int i=1;i<=n;i++){if(pt[color[i]]==1)printf("%02d:%02d %02d:%02d\n",t[i].be/60,t[i].be%60,t[i].en/60,t[i].en%60);elseprintf("%02d:%02d %02d:%02d\n",t[i+n].be/60,t[i+n].be%60,t[i+n].en/60,t[i+n].en%60);}}}return 0;
}