[POJ3683]Priest John’s Busiest Day【2-SAT】

Priest John’s Busiest Day

【题目描述】

传送门

【题目大意】

有n对新人要举行仪式,每对都有两个时间段可以选择,问是否可以所有新人的仪式时间不重叠。

【题解】

我们将时间段看成点,如果两个时间段相交,那么与另一个时间段连边。然后2-SAT就可以了。

【代码如下】

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int n,Top,Stk[MAXN<<1];
bool vis[MAXN<<1];
struct xcw{
    int x,y,z;
    bool operator <(const xcw b)const{return x<b.x||x==b.x&&y<=b.y;}
}a[MAXN];
struct Edge{
    int tot,lnk[MAXN<<1],nxt[MAXN*MAXN<<1],son[MAXN*MAXN<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
bool check(int s1,int t1,int s2,int t2){if(t1<=s2||t2<=s1) return 1;return 0;}
bool DFS(int x){
    if(vis[x^1]) return 0;
    if(vis[x]) return 1;
    vis[x]=1;Stk[++Top]=x;
    for(int j=E.lnk[x];j;j=E.nxt[j]) if(!DFS(E.son[j])) return 0;
    return 1;
}
bool Solve(){
    for(int i=0;i<n;i++)
    if(!vis[i<<1]&&!vis[i<<1|1]){
        Top=0;
        if(!DFS(i<<1)){
            while(Top) vis[Stk[Top--]]=0;
            if(!DFS(i<<1|1)) return 0;
        }
    }
    return 1;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=0,h,s;i<n;i++){
        scanf("%d:%d",&h,&s),a[i].x=h*60+s;
        scanf("%d:%d",&h,&s),a[i].y=h*60+s;
        scanf("%d",&a[i].z);
    }
    for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++){
        if(!check(a[i].x,a[i].x+a[i].z,a[j].x,a[j].x+a[j].z)) E.Add(i<<1,j<<1|1),E.Add(j<<1,i<<1|1);
        if(!check(a[i].x,a[i].x+a[i].z,a[j].y-a[j].z,a[j].y)) E.Add(i<<1,j<<1),E.Add(j<<1|1,i<<1|1);
        if(!check(a[i].y-a[i].z,a[i].y,a[j].x,a[j].x+a[j].z)) E.Add(i<<1|1,j<<1|1),E.Add(j<<1,i<<1);
        if(!check(a[i].y-a[i].z,a[i].y,a[j].y-a[j].z,a[j].y)) E.Add(i<<1|1,j<<1),E.Add(j<<1|1,i<<1);
    }
    if(!Solve()) printf("NO\n");
    else{
        printf("YES\n");
        for(int i=0;i<n;i++)
        if(vis[i<<1]) printf("%02d:%02d %02d:%02d\n",a[i].x/60,a[i].x%60,(a[i].x+a[i].z)/60,(a[i].x+a[i].z)%60);
        else printf("%02d:%02d %02d:%02d\n",(a[i].y-a[i].z)/60,(a[i].y-a[i].z)%60,a[i].y/60,a[i].y%60);
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部