本题可以看出来是2-sat。
难点在于输出一种可行解。
我们想tarjan在这里的作用是什么？缩点。
何为缩点，即把点都放到一个强连通分量里视为一个块，然后对块跑拓扑即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int N=1e4+10; 10 struct edge{ int to,nex;}e[8000006]; 11 struct tim{ int a,b;}t[N]; 12 int n,head[N],low[N],dfn[N],opp[N],col[N],vis[N],ans[N],in[N],s[N],len[N],top,num,cnt,ccnt; 13 vector E[N]; 14 queue q; 15 bool wrong(int x,int y) 16 { 17 if(t[x].b<=t[y].a||t[y].b<=t[x].a)return 0; 18 return 1; 19 } 20 void init() 21 { 22 ccnt=num=top=cnt=0; 23 memset(head,0,sizeof(head)); 24 memset(low,0,sizeof(low)); 25 memset(dfn,0,sizeof(dfn)); 26 memset(opp,0,sizeof(opp)); 27 memset(col,0,sizeof(col)); 28 memset(vis,0,sizeof(vis)); 29 memset(in,0,sizeof(in)); 30 memset(ans,-1,sizeof(ans)); 31 } 32 void dfs(int x) 33 { 34 s[++top]=x;low[x]=dfn[x]=++cnt;vis[x]=1; 35 for(int i=head[x];i;i=e[i].nex) 36 { 37 int y=e[i].to; 38 if(!dfn[y]) 39 { 40 dfs(y);low[x]=min(low[x],low[y]); 41 } 42 else if(vis[y])low[x]=min(low[x],dfn[y]); 43 } 44 if(low[x]==dfn[x]) 45 { 46 ++num;int a; 47 while(s[top+1]!=x) 48 { 49 int a=s[top--]; 50 col[a]=num; 51 vis[a]=0; 52 } 53 54 } 55 return; 56 } 57 void solve() 58 { 59 for(int i=1;i<=n*2;++i) 60 { 61 if(!dfn[i])dfs(i); 62 } 63 return; 64 } 65 void add(int x,int y) 66 { 67 e[++ccnt].to=y;e[ccnt].nex=head[x];head[x]=ccnt; 68 } 69 void toposort() 70 { 71 for(int i=1;i<=2*n;++i) 72 { 73 for(int j=head[i];j;j=e[j].nex) 74 { 75 int y=e[j].to; 76 if(col[y]==col[i])continue; 77 E[col[y]].push_back(col[i]); 78 in[col[i]]++; 79 } 80 } 81 for(int i=1;i<=num;++i) 82 { 83 if(!in[i])q.push(i); 84 } 85 while(!q.empty()) 86 { 87 int x=q.front();q.pop(); 88 if(ans[x]==-1) 89 { 90 ans[x]=1;ans[opp[x]]=0; 91 } 92 for(int i=E[x].size()-1;i>=0;--i) 93 { 94 in[E[x][i]]--; 95 if(in[E[x][i]]==0)q.push(E[x][i]); 96 } 97 } 98 return; 99 }100 int main()101 {102 while(~scanf("%d",&n))103 {104 init();int a,b,c,d;105 for(int i=1;i<=n;++i)106 {107 scanf("%d:%d %d:%d %d",&a,&b,&c,&d,&len[i]);108 t[i].a=a*60+b;109 t[i+n].b=c*60+d;110 t[i].b=t[i].a+len[i];111 t[i+n].a=t[i+n].b-len[i];112 }113 for(int i=1;i<=n;++i)114 for(int j=1;j<=n;++j)115 {116 if(i==j)continue;117 if(wrong(i,j))add(i,j+n);118 if(wrong(i,j+n))add(i,j);119 if(wrong(i+n,j))add(i+n,j+n);120 if(wrong(i+n,j+n))add(i+n,j);121 }122 solve();123 for(int i=1;i<=n;++i)124 {125 if(col[i]==col[i+n]){126 puts("NO");return 0;127 }128 opp[col[i]]=col[i+n];129 opp[col[i+n]]=col[i];130 }131 puts("YES");132 toposort();133 for(int i=1;i<=n;++i)134 {135 if(ans[col[i]]==1) printf("%.2d:%.2d %.2d:%.2d\n",t[i].a/60,t[i].a%60,t[i].b/60,t[i].b%60);136 else printf("%.2d:%.2d %.2d:%.2d\n",t[i+n].a/60,t[i+n].a%60,t[i+n].b/60,t[i+n].b%60);137 }138 }139 return 0;140 }