首页 > 代码库 > POJ 3683 Priest John's Busiest Day (2-SAT)
POJ 3683 Priest John's Busiest Day (2-SAT)
题意:有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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。