POJ 3683 Priest John's Busiest Day[2-SAT 构造解]

时间:2021-11-17 09:09:13

题意:

$n$对$couple$举行仪式,有两个时间段可以选择,问是否可以不冲突举行完,并求方案


两个时间段选择对应一真一假,对于有时间段冲突冲突的两人按照$2-SAT$的规则连边(把不冲突的时间段连起来)

然后本题需要构造解,所以要$SCC$缩点反向建图记录否定再拓扑排序$dfs$染色,好麻烦...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=,M=1e6+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m;
struct person{
int a,b;
}p[N];
struct edge{
int v,ne;
}e[M],e2[M];
int h[N],h2[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
inline void ins2(int u,int v){
cnt++;
e2[cnt].v=v;e2[cnt].ne=h2[u];h2[u]=cnt;
}
inline bool isIn(int x,int y){
if(p[x].b<=p[y].a||p[x].a>=p[y].b) return false;
return true;
}
void buildGraph(){
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
int x=i<<,y=j<<;
if(isIn(x-,y-)) ins(x-,y),ins(y-,x);
if(isIn(x-,y)) ins(x-,y-),ins(y,x);
if(isIn(x,y-)) ins(x,y),ins(y-,x-);
if(isIn(x,y)) ins(x,y-),ins(y,x-);
}
}
int dfn[N],low[N],dfc,belong[N],scc;
int st[N],top;
void dfs(int u){
dfn[u]=low[u]=++dfc;
st[++top]=u;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!belong[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
scc++;
while(true){
int x=st[top--];
belong[x]=scc;
if(x==u) break;
}
}
}
bool judge(){
for(int i=;i<=n;i++) if(belong[i<<]==belong[(i<<)-]) return false;
return true;
}
int ind[N];
void rebuildGraph(){
int _=n<<;
cnt=;
for(int u=;u<=_;u++)
for(int i=h[u];i;i=e[i].ne)
if(belong[u]!=belong[e[i].v])
ins2(belong[e[i].v],belong[u]),ind[belong[u]]++;
}
int color[N];
void dfsCol(int u){
if(color[u]) return;
color[u]=;
for(int i=h2[u];i;i=e2[i].ne) dfsCol(e2[i].v);
}
int opp[N];
void topoSort(){
top=;
for(int i=;i<=scc;i++) if(!ind[i]) st[++top]=i;
while(top){
int u=st[top--];
if(color[u]) continue;
color[u]=;dfsCol(opp[u]);
for(int i=h2[u];i;i=e2[i].ne){
int v=e2[i].v;
ind[v]--;
if(!ind[v]) st[++top]=v;
}
}
}
void print(int a,int b){
printf("%.2d:%.2d ",a/,a%);
printf("%.2d:%.2d ",b/,b%);
puts("");
}
int main(){
freopen("in","r",stdin);
n=read();
for(int i=;i<=n;i++){
int x=i<<,t;
t=read();
p[x-].a=t*+read();
t=read();
p[x].b=t*+read();
t=read();
p[x-].b=p[x-].a+t;
p[x].a=p[x].b-t;
}
buildGraph();
int _=n<<;
for(int i=;i<=_;i++) if(!dfn[i]) dfs(i);
if(!judge()) puts("NO");
else{
puts("YES");
rebuildGraph();
for(int i=;i<=n;i++){
int x=i<<;
opp[belong[x]]=belong[x-];
opp[belong[x-]]=belong[x];
}
topoSort();
for(int i=;i<=n;i++){
int x=i<<;
if(color[belong[x]]==) print(p[x].a,p[x].b);
else print(p[x-].a,p[x-].b);
}
}
}