wordpress 新闻采集站/泰安seo培训
Description
约翰是街区里唯一的神父。假设有n对新人打算在同一天举行结婚仪式。第i对新人的结婚仪式的时间为Si到Ti，在其仪式开始时或是结束时需要进行一个用时为Di的特别仪式（也就是从Si到Si+Di或是从Ti-Di到Ti），该特别仪式需要神父在场。请判断是否可以通过合理安排每个仪式在开始时或是在结束时进行，从而保证神父能够出席所有的特别仪式。如果可能的话，请输出出席各个特别仪式的时间。当然，神父不可能出席多个仪式，不过神父前往仪式的途中所花费的时间可以忽略不计，神父可以在出席完一个特别仪式后，立即出席另一个开始时间与其结束时间相等的特别仪式
Input
第一行为一个整数n表示举行结婚仪式的新人对数，之后n行每行为每个仪式对应的Si，Ti与Di
Output
如果存在可行方案，输出YES并输出出席各个特别仪式的时间，否则输出NO
Sample Input
2
08:00 09:00 30
08:15 09:00 20
Sample Output
YES
08:00 08:30
08:40 09:00
Solution
2-SAT判断可行性，定义变量Xi为在开始时进行第i组新人的特别仪式
如果Si~Si+Di与Sj~Sj+Dj冲突，则Xi->~Xj,Xj->~Xi
如果Si~Si+Di与Ti -Di~Ti冲突，则Xi->Xj,~Xj->~Xi
如果Ti -Di~Ti与Sj~Sj+Dj冲突，则Xj->Xi,~Xi->~Xj
如果Ti -Di~Ti与Tj -Dj~Tj冲突，则~Xi->Xj,~Xj->Xi
用上述关系构图后只要用tarjan算法求强联通分量并判断是否有使得布尔公式值为真的一组布尔变量赋值即可
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<cmath>
#define maxn 2222
using namespace std;
vector<int>g[maxn];
stack<int>st;
int n,scc,index;
int low[maxn],dfn[maxn],instack[maxn],fa[maxn];
int S[maxn],T[maxn],D[maxn];
void init()//初始化
{ scc=index=0; while(!st.empty())st.pop(); for(int i=0;i<maxn;i++)g[i].clear(); memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); memset(low,0,sizeof(low));
}
void tarjan(int u)//求强联通分量
{ dfn[u]=low[u]=++index; instack[u]=1; st.push(u); int v,size=g[u].size(); for(int i=0;i<size;i++) { v=g[u][i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { scc++; do { v=st.top(); st.pop(); fa[v]=scc; instack[v]=0; }while(v!=u); }
}
bool check()
{for(int i=0;i<2*n;i++)//求强联通分量 if(!dfn[i])tarjan(i);for(int i=0;i<n;i++)//判断可行性 if(fa[i]==fa[n+i])//矛盾 return false;return true;
}
int main()
{scanf("%d",&n);init();for(int i=0;i<n;i++){int s1,s2,t1,t2;scanf("%d:%d%d:%d%d",&s1,&s2,&t1,&t2,&D[i]);//将时刻转化为分钟后记录 S[i]=s1*60+s2;T[i]=t1*60+t2;}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])){g[i].push_back(n+j);g[j].push_back(n+i);}if(min(S[i]+D[i],T[j])>max(S[i],T[j]-D[j])){g[i].push_back(j);g[n+j].push_back(n+i);}if(min(S[j]+D[j],T[i])>max(S[j],T[i]-D[i])){g[j].push_back(i);g[n+i].push_back(n+j);}if(min(T[i],T[j])>max(T[i]-D[i],T[j]-D[j])){g[n+i].push_back(j);g[n+j].push_back(i);}}if(check())//存在可行方案 {printf("YES\n");for(int i=0;i<n;i++){if(fa[i]<fa[n+i])printf("%02d:%02d %02d:%02d\n",S[i]/60,S[i]%60,(S[i]+D[i])/60,(S[i]+D[i])%60);elseprintf("%02d:%02d %02d:%02d\n",(T[i]-D[i])/60,(T[i]-D[i])%60,T[i]/60,T[i]%60);}}else//不存在可行方案 printf("NO\n");return 0;
}