强连通算法推断是否满足2-sat，然后反向建图，拓扑排序+染色。

一种选择是从 起点開始，还有一种是终点-持续时间那个点 開始。

若2个婚礼的某2种时间线段相交，则有矛盾，建边。

easy出错的地方就在于推断线段相交。

若s1<e2&&s2<e1则相交

输出路径的做法能够參考论文

#include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define MAXN 5555#define MAXM 3000010struct node{ int to,next;}edge[MAXM];int head[MAXN],en;int low[MAXN],dfn[MAXN],stack[MAXN],cho[MAXN],top,set[MAXN],col,num,color[MAXN],counts[MAXN];bool vis[MAXN],instack[MAXN];int n;int m;void addedge(int a,int b){ edge[en].to=b; edge[en].next=head[a]; head[a]=en++;}int son[MAXN];void tarjan(int u){ vis[u]=1; dfn[u]=low[u]=++num; instack[u]=true; stack[++top]=u; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!vis[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(dfn[v],low[u]); } if(dfn[u]==low[u]) { int j; col++; do { j=stack[top--]; instack[j]=false; set[j]=col; } while (j!=u); }}void init(){ en=top=col=num=0; memset(head,-1,sizeof(head)); memset(instack,0,sizeof(instack)); memset(vis,0,sizeof(vis)); memset(set,-1,sizeof(set)); memset(color,0,sizeof(color)); memset(counts,0,sizeof(counts)); memset(cho,0,sizeof(cho));}struct node2{ int st,ed,la;}p[2005];vector
            
              g[2005];void topsort(){ queue
             
               q; for(int i=1;i<=col;i++) { if(counts[i]==0) q.push(i); } while(!q.empty()) { int j=q.front(); if(!color[j]) color[j]=1,color[son[j]]=-1; q.pop(); for(int k=0;k
              
               p[j].st) {addedge(i,j+n);} if(p[i].st
               
                p[j].ed-p[j].la) {addedge(i,j);} if(p[i].ed-p[i].la
                
                 p[j].st) {addedge(i+n,j+n);} if(p[i].ed-p[i].la
                 
                  p[j].ed-p[j].la) {addedge(i+n,j);} } } for(int i=1;i<=n*2;i++) if(!vis[i])tarjan(i); int ok=1; for(int i=1;i<=n;i++) { if(set[i]==set[i+n]) {ok=0;break;} son[set[i]]=set[i+n]; son[set[i+n]]=set[i]; } if(ok==0) {puts("NO");continue;} else puts("YES"); for(int i=1;i<=col;i++) g[i].clear(); for(int i=1;i<=2*n;i++) for(int j=head[i];~j;j=edge[j].next) if(set[i]!=set[edge[j].to]) { g[set[edge[j].to]].push_back(set[i]); counts[set[i]]++; } topsort(); for(int i=1;i<=2*n;i++) { if(color[set[i]]==1) cho[i]=1; } for(int i=1;i<=n;i++) { if(cho[i]) print(p[i].st,p[i].st+p[i].la); else print(p[i].ed-p[i].la,p[i].ed); } } return 0;}/*308:00 09:00 3008:15 09:00 2008:00 09:00 30*/