首页 > 代码库 > poj 3683 Priest John's Busiest Day 2-sat
poj 3683 Priest John's Busiest Day 2-sat
#include<cstdio>#include<algorithm>#include<vector>#include<cstring>#include<stack>using namespace std;const int maxn = 2000 + 30;vector<int> G[maxn], G2[maxn];vector<int> S;int vis[maxn], sccno[maxn], scc_cnt;int n,m;int s[maxn],t[maxn],d[maxn];void dfs1(int u){ if(vis[u]) return; vis[u] = 1; for(int i = 0; i < G[u].size(); i++) dfs1(G[u][i]); S.push_back(u);}void dfs2(int u){ if(sccno[u]) return; sccno[u] = scc_cnt; for(int i = 0; i < G2[u].size(); i++) dfs2(G2[u][i]);}void find_scc(int n){ int i; scc_cnt = 0; S.clear(); memset(sccno, 0, sizeof(sccno)); memset(vis, 0, sizeof(vis)); for(i = 0; i < n; i++) dfs1(i); for(i = n-1; i >= 0; i--) if(!sccno[S[i]]) { scc_cnt++; dfs2(S[i]); }}int main(){ while(scanf("%d",&n)!=EOF) { int i,j; int x,y; for(i=0;i<2*n;i++) { G[i].clear(); G2[i].clear(); } for(i=0;i<n;i++) { scanf("%d:%d",&x,&y); s[i]=x*60+y; scanf("%d:%d",&x,&y); t[i]=x*60+y; scanf("%d",&d[i]); } for(i=0;i<n;i++) for(j=i+1;j<n;j++) { if( !( s[j]>=s[i]+d[i] || s[j]+d[j]<=s[i] ) ) { G[i].push_back(j+n); G2[j+n].push_back(i); G[j].push_back(i+n); G2[i+n].push_back(j); } if( !( t[j]-d[j]>=s[i]+d[i] || t[j]<=s[i] ) ) { G[i].push_back(j); G2[j].push_back(i); G[j+n].push_back(i+n); G2[i+n].push_back(j+n); } if( !( t[j]-d[j]>=t[i] || t[j]<=t[i]-d[i] ) ) { G[i+n].push_back(j); G2[j].push_back(i+n); G[j+n].push_back(i); G2[i].push_back(j+n); } if( !( t[i]-d[i]>=s[j]+d[j] || t[i]<=s[j] ) ) { G[i+n].push_back(j+n); G2[j+n].push_back(i+n); G[j].push_back(i); G2[i].push_back(j); } } find_scc(2*n); int flag=1; for(i=0;i<n;i++) { if(sccno[i]==sccno[i+n]) { printf("NO\n"); flag=0; break; } } if(flag) { printf("YES\n"); for(i=0;i<n;i++) { if(sccno[i]>sccno[i+n]) 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); } } } return 0;}
poj 3683 Priest John's Busiest Day 2-sat
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。