首页 > 代码库 > POJ 3683 Priest John's Busiest Day (2-SAT)

POJ 3683 Priest John's Busiest Day (2-SAT)

2024-07-18 06:18:37   219人阅读

题意：有n对新人要在同一天结婚。结婚时间为Ti到Di，这里有时长为Si的一个仪式需要神父出席。神父可以在Ti-（Ti+Si）这段时间出席也可以在（Di-Si）-Si这段时间。问神父能否出席所有仪式，如果可以输出一组时间安排。

思路：2-SAT。神父可以在开始出席也可以在结束时候出席，要求与其他出席时间没有冲突，这样建图计算即可。另一一定要弄清楚true和false代表的含义。

#include <cstdio>#include <cmath>#include <vector>#include <cstring>#include <string>#include <iostream>using namespace std;const int maxn =1005;struct TwoSAT{    int n;    vector<int> G[maxn*2];    bool mark[maxn*2];    int S[maxn*2],c;    bool dfs(int x)    {        if(mark[x^1]) return false;        if(mark[x]) return true;        mark[x]=true;        S[c++]=x;        for(int i=0; i<G[x].size(); ++i)            if(!dfs(G[x][i])) return false;        return true;    }    void init(int n)    {        this->n=n;        for(int i=0; i<n*2; ++i) G[i].clear();        memset(mark,0,sizeof(mark));    }    void add_clause(int x,int xval,int y,int yval)    {        x=x*2+xval;        y=y*2+yval;        G[x^1].push_back(y);        G[y^1].push_back(x);    }    bool solve()    {        for(int i=0; i<n*2; i+=2)        {            if(!mark[i]&&!mark[i+1])            {                c=0;                if(!dfs(i))                {                    while(c>0) mark[S[--c]]=false;                    if(!dfs(i+1)) return false;                }            }        }        return true;    }};TwoSAT solver;bool judge(int st1,int ed1,int st2,int ed2){    if(st1<=st2&&ed2<=ed1) return true;    if(st2<=st1&&ed1<=ed2) return true;    if(st1<st2&&st2<ed1&&ed2>ed1) return true;    if(st2<st1&&st1<ed2&&ed1>ed2) return true;    return false;}int TimetoInt(string str){    int t=((str[0]-‘0‘)*10+(str[1]-‘0‘))*60+(str[3]-‘0‘)*10+(str[4]-‘0‘);    return t;}string InttoTime(int t){    string str;    int a=t/60,b=t%60;    str+=(a/10+‘0‘);    str+=(a%10+‘0‘);    str+=‘:‘;    str+=(b/10+‘0‘);    str+=(b%10+‘0‘);    return str;}int cost[1005],t[1005][2];int n;bool solve(){    solver.init(n);    for(int i=0; i<n; ++i)for(int a=0; a<2; ++a)            for(int j=i+1; j<n; ++j) for(int b=0; b<2; ++b)                {                    int ast,aed;                    int bst,bed;                    if(a==1) ast=t[i][a],aed=t[i][a]+cost[i];                    else ast=t[i][a]-cost[i],aed=t[i][a];                    if(b==1)bst=t[j][b],bed=t[j][b]+cost[j];                    else bst=t[j][b]-cost[j],bed=t[j][b];                    if(judge(ast,aed,bst,bed))                        solver.add_clause(i,a^1,j,b^1);                }    return solver.solve();}int main(){    while(cin>>n)    {        for(int i=0; i<n; ++i)        {            string st,ed;            cin>>st>>ed>>cost[i];            t[i][1]=TimetoInt(st);            t[i][0]=TimetoInt(ed);        }        if(!solve()) cout<<"NO"<<endl;        else        {            cout<<"YES"<<endl;            for(int i=0; i<2*n; i+=2)            {                if(!solver.mark[i])                    cout<<InttoTime(t[i/2][1])<<" "<<InttoTime(t[i/2][1]+cost[i/2])<<endl;                else                    cout<<InttoTime(t[i/2][0]-cost[i/2])<<" "<<InttoTime(t[i/2][0])<<endl;            }        }    }    return 0;}
View Code

 


联系
我们