题意：一个小镇里面只有一个牧师，现在有些新人要结婚，需要牧师分别去主持一个仪式，给出每对新人婚礼的开始时间 s 和结束时间 t ，还有他们俩的这个仪式需要的时间（每对新人需要的时间长短可能不同） d ，牧师可以在婚礼开始的时间 d 内（s 到 s+d）或者是结束前的时间 d 内（t - d 到 t）完成这个仪式。现在问能否给出一种安排，让牧师能完成所有夫妇婚礼的仪式，如果可以，输出一种安排。

#include
#include
#include
#include
#include
#include
#include
#include
#include

int n,m,pre[2*maxn],lowlink[2*maxn],dfs_clock,sccno[2*maxn],scc_cnt;
int opp[2*maxn],st[2*maxn],ed[2*maxn],tt[2*maxn],indeg[2*maxn],color[2*maxn];

struct node{
int l,r;
}ne[2*maxn];
vector G[2*maxn],g[2*maxn];
stack S;

void tarjan(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
tarjan(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!sccno[v])
lowlink[u]=min(lowlink[u],pre[v]);
}

if(pre\[u\]==lowlink\[u\])  
{  
    scc\_cnt++;  
    for(;;)  
    {  
        int cur=S.top();S.pop();  
        sccno\[cur\]=scc\_cnt;  
        if(u==cur) break;  
    }  
}  

}

bool find_scc()
{
MM(pre,0);
MM(sccno,0);
MM(lowlink,0);
dfs_clock=scc_cnt=0;

for(int i=0;i<2\*n;i++)  
    if(!pre\[i\])  
      tarjan(i);

for(int i=0;i<2\*n;i++)  
    if(sccno\[i\]==sccno\[i^1\])  
        return false;  
return true;  

}

bool inter(node a,node b)
{
return a.r>b.l&&a.l<b.r;
}

void build()
{
for(int i=0;i<2*n;i++)
G[i].clear();

for(int i=0;i<2\*n;i++)  
   for(int j=i+1;j<2\*n;j++)//对任意两个点都进行下判断  
       if(inter(ne\[i\],ne\[j\]))  
      {  
        G\[i\].push\_back(j^1);  
        G\[j\].push\_back(i^1);  
      }  

}

void topsort()
{
MM(indeg,0);
MM(color,0);
for(int i=1;i<=scc_cnt;i++)
g[i].clear();

 for(int i=0;i<2\*n;i++)  
 {  
     opp\[sccno\[i\]\]=sccno\[i^1\];  
     opp\[sccno\[i^1\]\]=sccno\[i\];  
 }

 for(int u=0;u<2\*n;u++)  
     for(int i=0;i<G\[u\].size();i++)  
 {  
     int a=sccno\[u\],b=sccno\[G\[u\]\[i\]\];  
     if(a!=b)  
     {  
         indeg\[a\]++;  
         g\[b\].push\_back(a);  
     }  
 }

 queue<int> q;  
 for(int i=1;i<=scc\_cnt;i++)  
    if(!indeg\[i\]) q.push(i);

 while(q.size())  
 {  
     int u=q.front();q.pop();  
      if(!color\[u\])  
            {  
                color\[u\]=1;  
                color\[opp\[u\]\]=-1;  
            }  
     for(int i=0;i<g\[u\].size();i++)  
     {  
         int v=g\[u\]\[i\];  
         indeg\[v\]--;  
         if(!indeg\[v\]) q.push(v);  
     }  
 }

for(int i=0;i<n;i++)  
  if(color\[sccno\[i<<1\]\]==1)  
    printf("%02d:%02d %02d:%02d\\n",ne\[i<<1\].l/60,ne\[i<<1\].l%60,ne\[i<<1\].r/60,ne\[i<<1\].r%60);  
  else  
   printf("%02d:%02d %02d:%02d\\n",ne\[i<<1^1\].l/60,ne\[i<<1^1\].l%60,ne\[i<<1^1\].r/60,ne\[i<<1^1\].r%60);  

}

int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
int a,b,c,d,e;

      scanf("%d:%d %d:%d %d",&a,&b,&c,&d,&e);  
      ne\[i<<1\].l=a\*60+b;  
      ne\[i<<1\].r=a\*60+b+e;  
      ne\[i<<1^1\].l=60\*c+d-e;  
      ne\[i<<1^1\].r=60\*c+d;  
   }//针对每个点，其反点是^关系

   build();

   if(find\_scc())  
      {  
          printf("YES\\n");  
          topsort();  
      }  
   else printf("NO\\n");  
}  
return 0;  

}