分析
每场婚礼是一个变量,有“开始时举行方式”和“结束前举行仪式”两种取值,并看作节点i与i+n。
枚举每两个婚礼I,j若两者的时间有重叠,则说明二者不能同时被选为最终赋值,转化为2-SAT的边形式。
然后用Tarjan计算SCC然后输出方案即可。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+5,maxm=2e6+6,kinf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Graph{
int tot,head[maxn];
struct Edge{ int ver,next;}edge[maxm] ;
void add(int u,int v) {
edge[++tot].ver=v; edge[tot].next=head[u];
head[u]=tot; return ;
}
int low[maxn],dfn[maxn],num;
int stck[maxn],ins[maxn],top;
vector<int> scc[maxn]; int cnt,c[maxn],opp[maxn];
void tarjan(int x) {
low[x]=dfn[x]=++num;
stck[++top]=x; ins[x]=1;
for(int i=head[x],y;i;i=edge[i].next) {
if(!dfn[y=edge[i].ver]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]) {
cnt++; int z;
do{
z=stck[top--]; ins[z]=0;
c[z]=cnt; scc[cnt].push_back(z);
}while(z!=x);
}
}
}g;
int ar[maxn][3],res[maxn];
int main(){
//ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++) {
int a,b;
scanf("%d:%d",&a,&b);
ar[i][0]=a*60+b;
scanf("%d:%d",&a,&b);
ar[i][1]=a*60+b;
cin>>ar[i][2];
} //建边
for(int i=1;i<n;i++) {
for(int j=i+1;j<=n;j++) {
if(!(ar[i][0]>=ar[j][0]+ar[j][2]||ar[i][0]+ar[i][2]<=ar[j][0]) )
g.add(i,j+n),g.add(j,i+n);//0,0
if(!(ar[i][1]-ar[i][2]>=ar[j][0]+ar[j][2]||ar[i][1]<=ar[j][0]) )
g.add(i+n,j+n),g.add(j,i);//1,0
if(!(ar[i][0]>=ar[j][1]||ar[i][0]+ar[i][2]<=ar[j][1]-ar[j][2]) )
g.add(i,j),g.add(j+n,i+n);//0,1
if(!(ar[i][1]-ar[i][2]>=ar[j][1]||ar[i][1]<=ar[j][1]-ar[j][2]) )
g.add(i+n,j),g.add(j+n,i);//1,1
}
} //连通分量
for(int i=1;i<=2*n;i++) {
if(!g.dfn[i]) g.tarjan(i);
}
for(int i=1;i<=n;i++) {
if(g.c[i]==g.c[i+n]) { cout<<"NO\n"; return 0; }
g.opp[i]=i+n; g.opp[i+n]=i;
}
cout<<"YES\n";
for(int i=1;i<=n;i++) res[i]=g.c[i] > g.c[g.opp[i] ] ;
for(int i=1;i<=n;i++) {
if(res[i]==0) {
printf("%02d:%02d ",ar[i][0]/60,ar[i][0]%60) ;
printf("%02d:%02d\n",(ar[i][0]+ar[i][2])/60,(ar[i][0]+ar[i][2])%60);
} else {
printf("%02d:%02d ",(ar[i][1]-ar[i][2])/60,(ar[i][1]-ar[i][2])%60) ;
printf("%02d:%02d\n",ar[i][1]/60,ar[i][1]%60);
}
}
return 0;
}