题意：
有n场婚礼，每场婚礼的属性有开始时间，结束时间，和祷告持续时间，每场婚礼的祷告必须安排在婚礼的开始或者结束，问是否存在一种安排使得每场婚礼的祷告互不重叠，有的话输出安排方案。
分析：
n场婚礼，每场婚礼的祷告只能在开始或结束，2-sat问题，建图时采用互斥排定思想，即如果时间段i与时间段j互斥，则加i到非j、j到非i两条边。
代码：
//poj 3683
//sep9
#include <iostream>
#include <vector>
using namespace std;
const int maxN=2048;
vector<int> g[maxN],ng[maxN];
int n,m,cnt,scc,vis[maxN],dfn[maxN],cf[maxN],ans[maxN],color[maxN];
int start[maxN],end[maxN],d[maxN];
int cross(int a,int b,int c,int d)
{if(b<=c||d<=a)return 0;return 1;
}
void addegde(int u,int v)
{g[u].push_back(v);ng[v].push_back(u);
}void dfs(int k)
{vis[k]=1;for(int i=g[k].size()-1;i>=0;--i)if(!vis[g[k][i]])dfs(g[k][i]);dfn[++cnt]=k;
}void ndfs(int k)
{vis[k]=scc;for(int i=ng[k].size()-1;i>=0;--i)if(!vis[ng[k][i]])ndfs(ng[k][i]);
}
void kosaraju()
{memset(vis,0,sizeof(vis));cnt=0;for(int i=1;i<=2*n;++i)if(!vis[i])dfs(i); memset(vis,0,sizeof(vis));scc=0;for(int i=2*n;i>=1;--i)if(!vis[dfn[i]]){++scc;ndfs(dfn[i]);}
}int two_sat()
{int i,j;kosaraju();for(i=1;i<=n;++i)if(vis[i]==vis[i+n])return 0; else{cf[vis[i]]=vis[i+n];cf[vis[i+n]]=vis[i];}memset(color,0,sizeof(color)); for(i=scc;i>=1;--i) if(color[i]==0){color[i]=1;color[cf[i]]=-1;}memset(ans,0,sizeof(ans));for(i=1;i<=n;++i){if(color[vis[i]]==1)ans[i]=1;}return 1;
}int main()
{int i,j; scanf("%d",&n);for(i=1;i<=2*n;++i)g[i].clear(),ng[i].clear();for(i=1;i<=n;++i){int a,b;scanf("%d:%d",&a,&b);start[i]=a*60+b;scanf("%d:%d",&a,&b);end[i]=a*60+b;scanf("%d",&d[i]);}for(i=1;i<=n;++i)for(j=i+1;j<=n;++j){int a1=start[i],a2=start[i]+d[i];int b1=end[i]-d[i],b2=end[i];int c1=start[j],c2=start[j]+d[j];int d1=end[j]-d[j],d2=end[j]; if(cross(a1,a2,c1,c2)){addegde(i,j+n);addegde(j,i+n);}if(cross(a1,a2,d1,d2)){addegde(i,j);addegde(j+n,i+n);}if(cross(b1,b2,c1,c2)){addegde(i+n,j+n);addegde(j,i);}if(cross(b1,b2,d1,d2)){addegde(i+n,j);addegde(j+n,i);}}if(two_sat()==0){printf("NO");return 0;}elseprintf("YES\n"); for(i=1;i<=n;++i){int s,e;if(ans[i]==1)s=start[i],e=start[i]+d[i];elses=end[i]-d[i],e=end[i]; printf("%.2d:%.2d %.2d:%.2d\n",s/60,s%60,e/60,e%60);}return 0;
}