题意:有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; ; struct TwoSAT { int n; vector<]; ]; ],c; bool dfs(int x) { ]) return false; if(mark[x]) return true; mark[x]=true; S[c++]=x; ; i<G[x].size(); ++i) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; ; i<n*; ++i) G[i].clear(); memset(mark,,sizeof(mark)); } void add_clause(int x,int xval,int y,int yval) { x=x*+xval; y=y*+yval; G[x^].push_back(y); G[y^].push_back(x); } bool solve() { ; i<n*; i+=) { ]) { c=; if(!dfs(i)) { ) mark[S[--c]]=false; )) 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) { ]-+(str[]-+(str[]-+(str[]-'); return t; } string InttoTime(int t) { string str; ,b=t%; str+=(a/+'); str+=(a%+'); str+=':'; str+=(b/+'); str+=(b%+'); return str; } ],t[][]; int n; bool solve() { solver.init(n); ; i<n; ++i); a<; ++a) ; j<n; ++j) ; b<; ++b) { int ast,aed; int bst,bed; ) ast=t[i][a],aed=t[i][a]+cost[i]; else ast=t[i][a]-cost[i],aed=t[i][a]; )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^,j,b^); } return solver.solve(); } int main() { while(cin>>n) { ; i<n; ++i) { string st,ed; cin>>st>>ed>>cost[i]; t[i][]=TimetoInt(st); t[i][]=TimetoInt(ed); } if(!solve()) cout<<"NO"<<endl; else { cout<<"YES"<<endl; ; i<*n; i+=) { if(!solver.mark[i]) cout<<InttoTime(t[i/][])<<][]+cost[i/])<<endl; else cout<<InttoTime(t[i/][]-cost[i/])<<][])<<endl; } } } ; }