POJ3683PriestJohn'sBusiestDay(2

POJ 3683 Priest John's Busiest Day(2-SAT输出方案) http://poj.org/problem?id=3683 题意: 有N对新人举行婚,且每次婚需要持续d时间,从s时间到t时间之间举行且只能选择s到sd时间或t-d到t时间这两个完整的时间段举行.现在只有一个神父,问他有没有可能参加所

POJ 3683 Priest John's Busiest Day(2-SAT输出方案)

http://poj.org/problem?id=3683

题意:

有N对新人举行婚礼,且每次婚礼需要持续d时间,从s时间到t时间之间举行且只能选择s到s+d时间或t-d到t时间这两个完整的时间段举行.现在只有一个神父,问他有没有可能参加所有新人的婚礼(待完整段时间且任意两对新人的婚礼时间不重叠)? 输出一个可行的方案.

分析:

每对新人的婚礼时间只有两种选择,直接就可以转化为2-SAT问题.其中如果对于第i个婚礼与第j个婚礼来说:

假设i先办的时间区间为[a,b]而j后办的时间区间为[c,d],如何判断[a,b]与[c,d]是否发生了冲突呢?(边界相交不算).

只有下面两种情况下区间[s1,e1]与区间[s2,e2]才规范相交.

1. s1

2. s2

仔细一看上面两种情况是相同的,只要相交的两个区间的e1 e2 > s1 s2 即可保证这两个区间相交.

(仔细想想上面情况)

然后对于冲突的每对新人添加边即可.

AC代码:

#include
#include
#include
using namespace std;
const int maxn=1000+10;
struct Time
{
 int s,e,d;//开始,结束,持续
 Time(){}
 Time(int s,int e,int d):s(s),e(e),d(d){}
}t[maxn];
struct TwoSAT
{
 int n;
 vector G[maxn*2];
 int S[maxn*2],c;
 bool mark[maxn*2];

 bool dfs(int x)
 {
 if(mark[x^1]) return false;
 if(mark[x]) return true;
 mark[x]=true;
 S[c++]=x;
 for(int i=0;in=n;
 for(int i=0;i0) mark[S[--c]]=false;
 if(!dfs(i+1)) return false;
 }
 }
 return true;
 }
}TS;
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=0;i