题意:有\(n\)对情侣结婚,第i对情侣的婚礼从\(s_i\)时刻开始,\(t_i\)时刻结束,并且需要\(last_i\)分钟完成一项仪式,仪式要么在婚礼刚开始进行,要么在婚礼结束前进行,即必须选择\(s_i\)~\(s_i+last_i\)或者\(t_i-last_i\)~\(t_i\)两个时间段之一.求\(n\)对情侣能否全部完成仪式,如果能,输出一种具体方案.\(n<=1000.\)
在此之前,我们先来看一道名字一模一样,但有很大不同的题.洛咕
题意:有一个司仪，要主持\(n\)场婚礼，给出婚礼的起始时间和终止时间，每个婚礼需要超过一半的时间进行仪式，并且仪式不能终止.问司仪能否主持\(n\)场婚礼.\(n<=100000.\)
有没有发现两道题的不同:洛咕上这道题的仪式可以在任何时候开始,所以我们直接贪心来做就好了.把婚礼按照 开始时间+仪式持续时间 从小到大排序,然后从前往后扫,看每次婚礼能够在 结束时间之前 完成即可.注意一下:仪式持续时间=(婚礼开始时间+婚礼结束时间)/2+1,因为题目要求仪式超过婚礼一半时间,然后根据贪心,显然持续时间越短越好,所以就是这个式子.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
struct ppx{int s,t,last;}a[N];
inline bool cmp(ppx x,ppx y){return x.s+x.last<y.s+y.last;}
inline bool check(int n){
int cnt=0;
for(int i=1;i<=n;++i){
cnt=max(cnt,a[i].s)+a[i].last;
if(cnt>a[i].t)return false;
}
return true;
}
int main(){
while(1){
int n=read();if(!n)break;
for(int i=1;i<=n;++i){
a[i].s=read();a[i].t=read();
a[i].last=(a[i].t-a[i].s)/2+1;
}
sort(a+1,a+n+1,cmp);
if(check(n))puts("YES");
else puts("NO");
}
return 0;
}
咳咳,回到本题.因为只有两种选择,所以考虑\(2-SAT\),每次枚举两个婚礼的仪式时间,如果有重叠就连边.建图后跑\(Tarjan\),然后检查是否有\(i\)和\(i+n\)在同一个\(SCC\)里面即可.
至于输出方案,蓝书上的拓扑排序法我打挂了,就写的是一种更简单但是很难想到的方法.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=2005;
const int M=5e6+5;
int s[N],t[N],last[N],belong[N],val[N],opp[N];
int tot,head[N],nxt[M],to[M];
int tim,top,num,dfn[N],low[N],st[N],color[N];
inline bool pd(int l1,int r1,int l2,int r2){
if((l1>=l2&&l1<r2)||(r1>l2&&r1<=r2)||(l1<=l2&&r1>=r2))return 1;
return 0;
}
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u){
dfn[u]=low[u]=++tim;st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!color[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
color[u]=++num;
belong[u]=num;
while(st[top]!=u){
color[st[top]]=num;
belong[st[top]]=num;
--top;
}
--top;
}
}
int main(){
int n=read();
for(int i=1;i<=n;++i){
int a=read(),b=read(),c=read(),d=read();
s[i]=a*60+b;t[i]=c*60+d;last[i]=read();
}
for(int i=1;i<n;++i)
for(int j=i+1;j<=n;++j){
if(pd(s[i],s[i]+last[i],s[j],s[j]+last[j]))
add(i,j+n),add(j,i+n);
if(pd(s[i],s[i]+last[i],t[j]-last[j],t[j]))
add(i,j),add(j+n,i+n);
if(pd(t[i]-last[i],t[i],s[j],s[j]+last[j]))
add(i+n,j+n),add(j,i);
if(pd(t[i]-last[i],t[i],t[j]-last[j],t[j]))
add(i+n,j),add(j+n,i);
}
for(int i=1;i<=2*n;++i)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;++i){
if(belong[i]==belong[n+i]){puts("NO");return 0;}
opp[i]=n+i;opp[n+i]=i;
}
puts("YES");
for(int i=1;i<=n*2;++i)val[i]=belong[i]>belong[opp[i]];
for(int i=1;i<=n;++i){
if(!val[i])printf("%02d:%02d %02d:%02d\n",s[i]/60,s[i]%60,(s[i]+last[i])/60,(s[i]+last[i])%60);
else printf("%02d:%02d %02d:%02d\n",(t[i]-last[i])/60,(t[i]-last[i])%60,t[i]/60,t[i]%60);
}
return 0;
}