博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ - 3683 Priest John's Busiest Day
阅读量:4600 次
发布时间:2019-06-09

本文共 2448 字,大约阅读时间需要 8 分钟。

2-sat模板 输出方案

//Achen#include
#include
#include
#include
#include
#include
#include
#include
#include
const int N=2007;typedef long long LL;using namespace std;int n,st[N],ed[N];template
void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[N],nxt[N*N],to[N*N];void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;}int cnt,fi[N],nx[N*N],tt[N*N],in[N];void ADD(int u,int v) { nx[++cnt]=fi[u]; fi[u]=cnt; tt[cnt]=v; in[v]++;}int xj(int x,int y) { return !(ed[x]<=st[y]||st[x]>=ed[y]);}int tot,dfs_clock,dfn[N],low[N],que[N],top,bl[N];void tarjan(int x) { que[++top]=x; dfn[x]=low[x]=++dfs_clock; for(int i=fir[x];i;i=nxt[i]) { if(!dfn[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } else if(!bl[to[i]]) low[x]=min(low[x],dfn[to[i]]); } if(low[x]==dfn[x]) { tot++; while(top) { int tp=que[top--]; bl[tp]=tot; if(tp==x) break; } }}int vis[N],op[N]; void dfs(int x) { if(vis[x]) return; vis[x]=-1; for(int i=fi[x];i;i=nx[i]) dfs(tt[i]);}void tpsort() { top=0; for(int i=1;i<=tot;i++) if(!in[i]) que[++top]=i; while(top) { int x=que[top--]; if(vis[x]) continue; vis[x]=1; dfs(op[x]); for(int i=fi[x];i;i=nx[i]) { int y=tt[i]; in[y]--; if(!in[y]) que[++top]=y; } } }void print(int x) { printf("%.2d:",x/60); printf("%.2d ",x%60);}int main() {#ifdef DEBUG freopen(".in","r",stdin); freopen(".out","w",stdout);#endif read(n); for(int i=1;i<=n;i++) { int x,y,z; read(x); read(y); st[i<<1]=x*60+y; read(x); read(y); ed[i<<1|1]=x*60+y; read(z); ed[i<<1]=st[i<<1]+z; st[i<<1|1]=ed[i<<1|1]-z; } for(int i=2;i<=2*n+1;i++) for(int j=i+1;j<=2*n+1;j++) if(i!=j&&(i!=(j^1))&&xj(i,j)) add(i,j^1),add(j,i^1); for(int i=2;i<=2*n+1;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) { if(bl[i<<1]==bl[i<<1|1]) { puts("NO"); return 0; } else { op[bl[i<<1]]=bl[i<<1|1]; op[bl[i<<1|1]]=bl[i<<1]; } } puts("YES"); for(int i=2;i<=2*n+1;i++) for(int j=fir[i];j;j=nxt[j]) if(bl[i]!=bl[to[j]]) ADD(bl[to[j]],bl[i]); tpsort(); for(int i=1;i<=n;i++) { if(vis[bl[i<<1]]==1) { print(st[i<<1]); printf(" "); print(ed[i<<1]); puts(""); } else { print(st[i<<1|1]); printf(" "); print(ed[i<<1|1]); puts(""); } } return 0;}
View Code

 

转载于:https://www.cnblogs.com/Achenchen/p/8127759.html

你可能感兴趣的文章
NGINX + PHP-FPM 502
查看>>
mysql数据备份与恢复
查看>>
Openstack API常用命令
查看>>
OpenSSL漏洞凶猛来袭 慧眼恶意代码监测应对有方
查看>>
C语言 喝汽水问题
查看>>
LINUX中搭建DNS服务器,实现正向、反向以及访问不同DNS解析
查看>>
SCCM2012 R2实战系列之十:解决WDS服务无法启动问题(错误1067:进程意外终止)...
查看>>
ubuntu 下安装 mysql
查看>>
关于k-means聚类算法的matlab实现
查看>>
Git分支2
查看>>
一键安装Gitlab后的备份、迁移与恢复
查看>>
因为本人工作繁忙,精力有限,本博客停止更新。有兴趣的博友可以关注我在CSDN上的主博客...
查看>>
SQL server查看触发器是否被禁用
查看>>
[C++基础]在构造函数内部调用构造函数
查看>>
跟随我在oracle学习php(8)
查看>>
Spring 3.1.0 Hibernate 3.0 Eclipse Spring WEB例子
查看>>
UVA-10212 The Last Non-zero Digit. 分解质因子+容斥定理
查看>>
求两个集合的交集,并集,差集
查看>>
Kotlin的语法糖(一)基础篇
查看>>
OkHttp源码分析
查看>>