题目链接：

题意：有n个婚礼要举行，但是只有一个牧师。第i个婚礼使用牧师的时间长为leni，可以在开始时或结束时使用。问能否使得n个婚礼均举行？

思路:对于婚礼i，i*2-1表示在开始使用牧师，i*2表示在结束使用牧师。枚举每一对不同的i和j：

（1）如果i*2-1和j*2-1冲突。连接i*2-1  j*2

（2）如果i*2-1和j*2冲突，连接i*2-1 j*2-1

（3）如果i*2和j*2-1冲突，连接i*2 j*2

（4）如果i*2和j*2冲突，连接i*2 j*2-1

 

#include 
     
       #include 
      
        #include 
       
         #define min(x,y) ((x)<(y)?(x):(y)) using namespace std;  struct node {     int v,next; };    const int MAX=4005; const int MAXE=5000005; node edges[MAXE]; int head[MAX],e; int dfn[MAX],low[MAX],visit[MAX],color[MAX],col[MAX]; int n,index,cnt; stack
        
          S; int deg[MAX],ans[MAX],p[MAX]; int head1[MAX],e1; node edges1[MAXE];    void Add(int u,int v) {     edges[e].v=v;     edges[e].next=head[u];     head[u]=e++; }  void Add1(int u,int v) {     edges1[e1].v=v;     edges1[e1].next=head1[u];     head1[u]=e1++; }  void Tarjan(int u) {     int i,v;      low[u]=dfn[u]=++index;S.push(u);visit[u]=1;     for(i=head[u];i!=-1;i=edges[i].next)     {         v=edges[i].v;         if(!dfn[v])         {             Tarjan(v);             low[u]=min(low[u],low[v]);         }         else if(visit[v]) low[u]=min(low[u],dfn[v]);     }     if(dfn[u]==low[u])     {         cnt++;         do         {             v=S.top();             S.pop();             visit[v]=0;             color[v]=cnt;         }while(u!=v);     } }  void init() {     memset(deg,0,sizeof(deg));     memset(head1,-1,sizeof(head1));     e1=0;     int i,u,v,x,y;     for(u=1;u<=2*n;u++)     {         for(i=head[u];i!=-1;i=edges[i].next)         {             v=edges[i].v;             if(color[v]!=color[u])             {                 x=color[v];                 y=color[u];                 Add1(x,y);                 deg[y]++;             }         }     }     while(!S.empty()) S.pop();     for(i=1;i<=cnt;i++) if(!deg[i]) S.push(i);     memset(p,0,sizeof(p));     while(!S.empty())     {         u=S.top();         S.pop();         if(!p[u]) p[u]=1,p[col[u]]=-1;         for(i=head1[u];i!=-1;i=edges1[i].next)         {             v=edges1[i].v;             if(--deg[v]==0) S.push(v);         }     }     memset(ans,0,sizeof(ans));     for(i=1;i<=n;i++)     {         if(p[color[i*2-1]]==1) ans[i]=1;     } }  int TWO_ST() {     int i;      memset(dfn,0,sizeof(dfn));     memset(visit,0,sizeof(visit));     index=cnt=0;     while(!S.empty()) S.pop();     for(i=1;i<=2*n;i++) if(!dfn[i]) Tarjan(i);     for(i=1;i<=n;i++)     {         if(color[i*2-1]==color[i*2]) return 0;         col[color[i*2-1]]=color[i*2];         col[color[i*2]]=color[i*2-1];     }     init();     return 1; }  struct Node {     int s,e,len; };  Node a[MAX];  void deal() {     if(!TWO_ST())     {         puts("NO");         return;     }     puts("YES");     int i,x,y;     for(i=1;i<=n;i++)     {         ans[i]?(x=a[i].s,y=a[i].s+a[i].len):(x=a[i].e-a[i].len,y=a[i].e);         printf("%02d:%02d %02d:%02d\n",x/60,x%60,y/60,y%60);     } }    int OK(int s1,int len1,int s2,int len2) {     return s1