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

acwing-371. 牧师约翰最忙碌的一天(2-SAT)「建议收藏」牧师约翰在 9 月 1 日这天非常的忙碌。有 N 对情侣在这天准备结婚,每对情侣都预先计划好了婚礼举办的时间,其中第 i 对情侣的婚礼从时刻 Si 开始,到时刻 Ti 结束。婚礼有一个必须的仪式:站在牧师面前聆听上帝的祝福。这个仪式要么在婚礼开始时举行,要么在结束时举行。第 i 对情侣需要 Di 分钟完成这个仪式,即必须选择 Si∼Si+Di 或 Ti−Di∼Ti 两个时间段之一。牧师想知道他能否满足每场婚礼的要求,即给每对情侣安排Si∼Si+Di 或 Ti−Di∼Ti,使得这些仪式的时

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

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

牧师约翰在 91 日这天非常的忙碌。

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

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

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

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

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

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

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

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

例如:一场仪式安排在 08:0009:00,另一场仪式安排在 09:0010: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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168608.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux下的apache2 + mysql5 + php4 + gd2 源码完整安装详解

    linux下的apache2 + mysql5 + php4 + gd2 源码完整安装详解

  • 【面试真经】2020年7月 Linux运维面试题(含答案版)

    【面试真经】2020年7月 Linux运维面试题(含答案版)一.在当前文件目录下,有文件file1查询file1里面空行的所在行号查询file2以abc结尾的行打印出file1文件第一行到第3行二.如何将本地80端口的请求转发到8080端口,当前的主机IP为192.168.2.1三.crontab如何设置在11月份的每天早上6点到12点中,每隔2个小时执行/usr/bin/httpd.sh怎么实现四.编写个shell脚本将/usr/local/test目录下大于100K的文件转移到/tmp目录下五.简述raid0ra

  • 利用远程外网服务器搭建代理服务器[通俗易懂]

    利用远程外网服务器搭建代理服务器[通俗易懂]安装CCProxy官网地址:http://www.ccproxy.com/下载安装即可,软件使用很简单。配置CCProxy配置端口基本上不需要配置什么,只要你将默认的端口改为你的端口号就行,不改可能会被其他软件扫描到。新增账号新增账号支持访问,具体权限可以看说明。选择你的远程服务器特别说明:你的服务器一定要配置安全组,否则端口无法访问。通过服务器中的teln…

  • 散列的基本概念

    散列的基本概念散列的基本概念什么是散列?为什么需要散列?散列是一种思想。与已经学过的其他数据结构相比较,向量是采用循秩访问(callbyrank)的访问方式,列表是采用循位置访问(callbyposition)的访问方式,二叉搜索树是采用循关键码访问(callbykey)的访问方式,散列与他们都不一样,是采用循值访问(callbyvalue)的访问方式。举个例子,你现在身处同济大学嘉定…

  • Poetry(1)Poetry介绍与安装

    Poetry(1)Poetry介绍与安装介绍Poetry是Python中的依赖管理和打包工具,当然它也可以配置虚拟环境。它允许您声明项目所依赖的库,并为您管理(安装/更新)它们。之前一直使用virtualenvwrapper管理虚拟

  • esid是什么意思_es unassigned

    esid是什么意思_es unassignedESN(ElectronicSerialNumbers):电子序列号。在CDMA系统中,是鉴别一个物理硬件设备唯一的标识。也就是说每个手机都用这个唯一的ID来鉴别自己,就跟人的身份证一样。一个ESN有32bits,也就是32/8=4bytes。ESN用8位的16进制来表示,如0x801EA066。随着CDMA移动设别的增多,ESN已经不够用了,所以推出了位数更多的MEID。M…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号