输出方案的2-sat
直接比较两个点强联通分量的编号，缩完点的图应该是有向无环图，根据原始做法是反图topsort出解，编号小的说明顺序在后，选择这个点符合定义。
#include#include #include #include #include #include using namespace std;struct node{ int x,y,next;}a[8100000];int len,last[2100];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len;}int z,dfn[2100],low[2100];int top,sta[2100];bool v[2100];int cnt,bel[2100];void SCC(int x){ dfn[x]=low[x]=++z; sta[++top]=x;v[x]=true; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(dfn[y]==0) { SCC(y); low[x]=min(low[x],low[y]); } else if(v[y]==true) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]) { int k;cnt++; do { k=sta[top];top--; v[k]=false; bel[k]=cnt; }while(k!=x); }}int n;char ss[10];struct point{ int st,ed;}p[2100];int sc(){ scanf("%s",ss+1);int slen=strlen(ss+1); int k1=0,k2=0,i=1; while(ss[i]!=':') k1=k1*10+ss[i]-'0',i++; i++;while(i<=slen)k2=k2*10+ss[i]-'0',i++; return k1*60+k2;}void pr(int g){ if(g/60<10)printf("0"); printf("%d",g/60); printf(":"); g%=60; if(g<10)printf("0"); printf("%d",g);}bool together(point p1,point p2){ if(p1.st>p2.st)swap(p1,p2); return p1.ed<=p2.st;}void conposition(){ bool b1,b2; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) { b1=together(p[i],p[j]), b2=together(p[i],p[j+n]); if(!b1&&!b2)ins(i,i+n); else if(!b1)ins(i,j+n); else if(!b2)ins(i,j); b1=together(p[i+n],p[j]), b2=together(p[i+n],p[j+n]); if(!b1&&!b2)ins(i+n,i); else if(!b1)ins(i+n,j+n); else if(!b2)ins(i+n,j); }}int w[1100];int main(){ scanf("%d",&n); int st,ed,L; for(int i=1;i<=n;i++) { st=sc(),ed=sc(),scanf("%d",&L); p[i].st=st,p[i].ed=st+L; p[i+n].st=ed-L,p[i+n].ed=ed; } conposition(); z=top=cnt=0; for(int i=1;i<=2*n;i++) if(dfn[i]==0)SCC(i); for(int i=1;i<=n;i++) { if(bel[i]==bel[i+n]){printf("NO\n");return 0;} w[i]=bel[i]>bel[i+n]; } printf("YES\n"); for(int i=1;i<=n;i++) { if(w[i]==0) pr(p[i].st),printf(" "),pr(p[i].ed); else pr(p[i+n].st),printf(" "),pr(p[i+n].ed); printf("\n"); } return 0;}