POJ 3683 Priest John's Busiest Day (2-SAT,常规)

题意:

  一些人要在同一天进行婚礼,但是牧师只有1个,每一对夫妻都有一个时间范围[s , e]可供牧师选择,且起码要m分钟才主持完毕,但是要么就在 s 就开始,要么就主持到刚好 e 结束。因为人数太多了,这些时间可能会重叠,可能还会完全包含,可能还没有交叉,各种情况。问牧师能否主持完全部人的婚礼,若可以,给出每对夫妻占用牧师的一个时间段(记得按所给的夫妻的顺序哦)。网址:yii666.com<

  主要步骤如下。文章来源地址https://www.yii666.com/article/764013.html

(1)先建原图,不管是否会冲突。

(2)找强连通分量来缩点,如果会冲突,这个时候应该发现。

(3)建个缩点后,原图的反向图。文章地址https://www.yii666.com/article/764013.html

(4)着色法标记所要输出的时间段。网址:yii666.com

(5)时间段按照所给每对夫妻的顺序来输出。

实现:

  (1)婚礼要么在s就开始,要么在e刚好结束,还有可能这对夫妻就要求从s-e都要主持呢。 先把时间给转换成分钟,每对夫妻拥有2个时间段。

  (2)接下来主要是建图,建图时只考虑“冲突”,即如果i*2和j*2冲突了,那么选i*2就必须选j*2+1。先不用顾着i*2和j*2+1是否冲突,只要将4种可能的组合列出来,建图,其他的交给强连通分量去做。

  (3)强连通分量承接第3步的重任,在求强连通分量时要顺便判断是否会冲突,当然这比较简单。

  (4)建反向图只是穷举原图中的每条边,判断是否在同个scc中,如果不是就可以建边了,将边反过来这么简单。

  (5)着色时还得将另外冲突的“全部“着其他颜色,那么根据已建好的反向图一直DFS下去,如果已经着色,可以退出了,别每次都深搜到底了,没必要。

  (6)时间段还得按所给夫妻顺序!那得再稍微处理一下。文章来源地址:https://www.yii666.com/article/764013.html

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=+;
int t1[N], t2[N], t3[N], t4[N]; //保存时间点
bool vis[N];
vector<int> vect[N*], rg[N*], scc[N*]; //分别是:原图,反向图,
stack<int> stac; //强连通分量必备
int lowlink[N*], dfn[N*], scc_no[N*], scc_cnt, dfn_clock; //强连通分量必备
int col[N*]; //用于着色
bool dele[N*]; //标记输出点 inline int to_time(int h, int m){return h*+m;}
inline bool conflict(int a,int b, int c, int d){if(b<=c || d<=a) return true;return false;} void get_graph(int n) //难在建图吧?
{
for(int i=; i<n*; i++) vect[i].clear();
for(int i=; i<n; i++)
{
for(int j=; j<n; j++) //考虑放在前面
{
if(i==j) continue;
if(!conflict(t1[i],t2[i], t1[j],t2[j])) vect[i*].push_back(j*+);
if(!conflict(t1[i],t2[i], t3[j],t4[j])) vect[i*].push_back(j*); if(!conflict(t3[i],t4[i], t1[j],t2[j])) vect[i*+].push_back(j*+);
if(!conflict(t3[i],t4[i], t3[j],t4[j])) vect[i*+].push_back(j*);
}
}
} void DFS(int x) //模板tarjan
{
stac.push(x);
dfn[x]=lowlink[x]=++dfn_clock;
for(int i=; i<vect[x].size(); i++)
{
int t=vect[x][i];
if(!dfn[t])
{
DFS(t);
lowlink[x]=min(lowlink[x],lowlink[t]);
}
else if(!scc_no[t]) lowlink[x]=min(lowlink[x],dfn[t]);
}
if(lowlink[x]==dfn[x])
{
scc[++scc_cnt].clear();
while(true)
{
int t=stac.top();stac.pop();
scc_no[t]=scc_cnt;
scc[scc_cnt].push_back(t);
if(t==x) break;
}
}
} int find_scc(int n) //求强连通分量,顺便检查是否满足条件
{
scc_cnt=dfn_clock=;
memset(lowlink,,sizeof(lowlink));
memset(dfn,,sizeof(dfn));
memset(scc_no,,sizeof(scc_no));
for(int i=; i<n; i++) if(!dfn[i]) DFS(i);
for(int i=; i<n; i+=) if(scc_no[i]==scc_no[i+]) return false; //检查是否冲突
return true;
} void build_rg(int n) //建反向图,为了要反向着色
{
for(int i=; i<n; i++) rg[i].clear(); for(int i=; i<n; i++)
{
for(int j=; j<vect[i].size(); j++)
{
int t=vect[i][j];
if(scc_no[i]!=scc_no[t]) //不属于同个强连通分量
rg[scc_no[t]].push_back(scc_no[i]);
}
}
} void del(int s) //删除的是反向边,之前已建好的rg图
{
while(!col[s])
{
col[s]=;
for(int i=; i<rg[s].size(); i++) del(rg[s][i]); //递归“删除”,按反向边的方向(即着其他颜色)
}
} void color()
{
memset(col,,sizeof(col));
for(int i=; i<=scc_cnt; i++) //没有按照拓扑顺序也能AC???
if(!col[i])
{
col[i]=;
del( scc_no[ scc[i][]%==?scc[i][]+:scc[i][]-]); //在第i个SCC中任取1点,取其对立点,再取其所在scc编号,进行着色
}
} void print(int n)
{
memset(dele,,sizeof(dele));
puts("YES");
for(int i=; i<scc_cnt; i++)
{
if(col[i]==) //col=2的都是要的,当然,选全部col=3也一样,因为对称
for(int j=; j<scc[i].size(); j++)
dele[scc[i][j] ]=true; //把所有要输出的点先标记出来
}
for(int i=; i<n; i++)
{
if(dele[i])
if(i%==) //取前段
{
int a=t1[i/]/;
int b=t1[i/]%;
int c=t2[i/]/;
int d=t2[i/]%;
printf("%02d:%02d %02d:%02d\n",a,b,c,d);
}
else //取后段
{
int a=t3[i/]/;
int b=t3[i/]%;
int c=t4[i/]/;
int d=t4[i/]%;
printf("%02d:%02d %02d:%02d\n",a,b,c,d);
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
int n, a, b, c, d, e, f, g;
while(~scanf("%d",&n))
{
memset(t1,,sizeof(t1));
memset(t2,,sizeof(t2));
memset(t3,,sizeof(t3));
memset(t4,,sizeof(t4));
for(int i=; i<n; i++)
{
scanf("%d %c %d %d %c %d %d",&a,&b,&c, &d,&e,&f, &g);
t1[i]=to_time(a,c); //时间转成分钟,分别有2种,t1t2表示在前的start和end,t3t4表示在后
t2[i]=to_time(a,c)+g;
t3[i]=to_time(d,f)-g;
t4[i]=to_time(d,f);
}
get_graph(n);
if(!find_scc(n<<)) {puts("NO");continue;}
build_rg(n*); //按缩点建新的反向图reverse_graph
color(); //着色完,所需要的点也就出结果了
print(n*);
}
return ;
}

AC代码

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png