本题可以看出来是2-sat。
难点在于输出一种可行解。
我们想tarjan在这里的作用是什么？缩点。
何为缩点，即把点都放到一个强连通分量里视为一个块，然后对块跑拓扑即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<vector> 7 #include<queue> 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<int>E[N]; 14 queue<int>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 ",t[i].a/60,t[i].a%60,t[i].b/60,t[i].b%60); 136 else printf("%.2d:%.2d %.2d:%.2d ",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 }