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

全栈程序员-站长 • 2022年8月9日下午1:36 • 未分类 • 阅读 4

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}