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

题意：

$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);

        }

    }

}