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;}