acwing-371. 牧师约翰最忙碌的一天(2-SAT)「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

牧师约翰在 9 月 1 日这天非常的忙碌。

有 N 对情侣在这天准备结婚，每对情侣都预先计划好了婚礼举办的时间，其中第 i 对情侣的婚礼从时刻 Si 开始，到时刻 Ti 结束。

婚礼有一个必须的仪式：站在牧师面前聆听上帝的祝福。

这个仪式要么在婚礼开始时举行，要么在结束时举行。

第 i 对情侣需要 Di 分钟完成这个仪式，即必须选择 Si∼Si+Di 或 Ti−Di∼Ti 两个时间段之一。

牧师想知道他能否满足每场婚礼的要求，即给每对情侣安排Si∼Si+Di 或 Ti−Di∼Ti，使得这些仪式的时间段不重叠。

若能满足，还需要帮牧师求出任意一种具体方案。

注意，约翰不能同时主持两场婚礼，且 所有婚礼的仪式均发生在 9 月 1 日当天。

如果一场仪式的结束时间与另一场仪式的开始时间相同，则不算重叠。

例如：一场仪式安排在 08:00∼09:00，另一场仪式安排在 09:00∼10:00，则不认为两场仪式出现重叠。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含 Si,Ti,Di，其中 Si 和 Ti 是 hh:mm 形式。

输出格式
第一行输出能否满足，能则输出 YES，否则输出 NO。

接下来 N 行，每行给出一个具体时间段安排。

数据范围
1≤N≤1000
输入样例：
2
08:00 09:00 30
08:15 09:00 20
输出样例：
YES
08:00 08:30
08:40 09:00

题解
2-SAT问题

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int M = 4e6 + 10;
int low[N],num[N],dfn;
int sta[N],in_sta[N],top;
int scc[N],sccno;
int head[N],cnt;
struct Edge{ 

int v,next;
}edge[M];
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void Tarjan(int u){ 

low[u] = num[u] = ++ dfn;
sta[top ++] = u,in_sta[u] = true;
for(int i = head[u];~i;i = edge[i].next){ 

int v = edge[i].v;
if(!num[v]){ 

Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(in_sta[v])low[u] = min(low[u],num[v]);
}
if(low[u] == num[u]){ 

sccno ++;
while(true){ 

int t = sta[-- top];
in_sta[t] = false;
scc[t] = sccno;
if(t == u)break;
}
}
}
bool check(int a,int b,int c,int d){ 

return !(c >= b || d <= a);
}
struct node{ 

int b1,e1,b2,e2;
}Node[N],Node1[N];
int get(int a,int b){ 

return a * 60 + b;
}
bool cmp1(const node &a,const node &b){ 

return a.b1 < b.b1;
}
int main(){ 

int n;
memset(head,-1,sizeof head);
cin>>n;
int x1,y1,x2,y2,d;
for(int i = 0;i < n;i ++){ 

scanf("%d:%d %d:%d %d",&x1,&y1,&x2,&y2,&d);
Node[i].b1 = get(x1,y1),Node[i].e1 = get(x1,y1) + d;
Node[i].b2 = get(x2,y2) - d,Node[i].e2 = get(x2,y2);
}
for(int i = 0;i < n;i ++){ 

for(int j = 0;j < n;j ++){ 

if(i == j)continue;
bool a = check(Node[i].b1,Node[i].e1,Node[j].b1,Node[j].e1);
bool b = check(Node[i].b1,Node[i].e1,Node[j].b2,Node[j].e2);
bool c = check(Node[i].b2,Node[i].e2,Node[j].b1,Node[j].e1);
bool d = check(Node[i].b2,Node[i].e2,Node[j].b2,Node[j].e2);
if(a ){ 

add(i * 2,j * 2 + 1);
}
if(b){ 

add(i * 2,j * 2);
}
if(c ){ 

add(i * 2 + 1,j * 2 + 1);
}
if(d){ 

add(i * 2 + 1,j * 2);
}
}
}
for(int i = 0;i < 2 * n;i ++){ 

if(!num[i])Tarjan(i);
}
for(int i = 0;i < n;i ++){ 

if(scc[2 * i] == scc[2 * i + 1]){ 

cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
for(int i = 0;i < n;i ++){ 

if(scc[2 * i] < scc[2 * i + 1]){ 

printf("%02d:%02d %02d:%02d\n",Node[i].b1 / 60,Node[i].b1 % 60,Node[i].e1 / 60,Node[i].e1 % 60);
}else printf("%02d:%02d %02d:%02d\n",Node[i].b2 / 60,Node[i].b2 % 60,Node[i].e2 / 60,Node[i].e2 % 60);
}
return 0;
}