首页 > 代码库 > POJ 3683 Priest John's Busiest Day（2-SAT）
POJ 3683 Priest John's Busiest Day（2-SAT）
【题目链接】 http://poj.org/problem?id=3683
【题目大意】
每个婚礼有两个时段可以进行特别仪式，特别仪式必须要有神父在场，
神父只有一个，问是否能满足所有婚礼的需求，
【题解】
因为两个时段必须要满足一个时段，所以如果一个时段被占用那么另一个时段必须被空出来，
我们根据各个婚礼两个时段之间的冲突关系建边，之后跑2-SAT，判断是否冲突，
若无冲突则输出方案。
【代码】
#include <cstdio>#include <algorithm>#include <vector>#include <cstring> using namespace std;const int MAX_V=10000;int V; //顶点数vector<int> G[MAX_V]; //图的邻接表表示vector<int> rG[MAX_V]; //反向图vector<int> vs; //后序遍历bool used[MAX_V];int cmp[MAX_V]; //所属强连通分量的拓扑序void add_edge(int from,int to){ G[from].push_back(to); rG[to].push_back(from);} void dfs(int v){ used[v]=1; for(int i=0;i<G[v].size();i++){ if(!used[G[v][i]])dfs(G[v][i]); }vs.push_back(v);}void rdfs(int v,int k){ used[v]=1; cmp[v]=k; for(int i=0;i<rG[v].size();i++){ if(!used[rG[v][i]])rdfs(rG[v][i],k); }}int scc(){ memset(used,0,sizeof(used)); vs.clear(); for(int v=0;v<V;v++){if(!used[v])dfs(v);} memset(used,0,sizeof(used)); int k=0; for(int i=vs.size()-1;i>=0;i--){ if(!used[vs[i]])rdfs(vs[i],k++); }return k;}const int MAX_N=1010; int N;int S[MAX_N],T[MAX_N],D[MAX_N];void solve(){ V=N*2; for(int i=0;i<N;i++){ for(int j=0;j<i;j++){ if(min(S[i]+D[i],S[j]+D[j])>max(S[i],S[j])){ add_edge(i,N+j); add_edge(j,N+i); } if(min(S[i]+D[i],T[j])>max(S[i],T[j]-D[j])){ add_edge(i,j); add_edge(j+N,i+N); } if(min(S[j]+D[j],T[i])>max(S[j],T[i]-D[i])){ add_edge(j,i); add_edge(i+N,j+N); } if(min(T[i],T[j])>max(T[i]-D[i],T[j]-D[j])){ add_edge(i+N,j); add_edge(j+N,i); } } }scc(); for(int i=0;i<N;i++){ if(cmp[i]==cmp[N+i]){ puts("NO"); return; } } puts("YES"); for(int i=0;i<N;i++){ if(cmp[i]>cmp[N+i]){ printf("%02d:%02d %02d:%02d\n",S[i]/60,S[i]%60,(S[i]+D[i])/60,(S[i]+D[i])%60); }else{ printf("%02d:%02d %02d:%02d\n",(T[i]-D[i])/60,(T[i]-D[i])%60,T[i]/60,T[i]%60); } }}int main(){ while(~scanf("%d",&N)){ for(int i=0;i<N;i++){ int HH,MM; scanf("%d:%d",&HH,&MM); S[i]=HH*60+MM; scanf("%d:%d",&HH,&MM); T[i]=HH*60+MM; scanf("%d",&D[i]); }solve(); }return 0;}
POJ 3683 Priest John's Busiest Day（2-SAT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。