【题目链接】
http://poj.org/problem?id=3683
【题目大意】
有个小镇上有n对夫妻要举办婚礼,每队夫妻都要请镇上的牧师举行一个仪式,但是镇上只有一个牧师,牧师一次只能为一对夫妻做仪式。
已知每队夫妻的婚礼的起始t1和结束的时间t2, 他们举办仪式的时间是d,仪式只能在婚礼开始的前d时间举行或者在结束之前的d内举行。问牧师能不能合理安排,使得每对夫妻都能举办仪式?
【思路】
对于每一对夫妻,他们要么在开始时做仪式,要么在结束时做仪式,所以是2-SAT模型。
这题要输出任一个方案,研究了好几个小时。。。
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define WHITE -1
#define RED 1
#define BLUE 0
using namespace std;
typedef long long int64;
const int MAXN = 1010;
const int VN = MAXN*2;
const int EN = 1000010;
int n;
struct Couple{
int d;
int t1, t2;
}arr[MAXN];
struct Edge{
int u, v, next;
};
void time_out(int t, int d){
printf("%02d:%02d %02d:%02d\n", t/60, t%60, (t+d)/60, (t+d)%60);
}
struct Graph{
int size;
int head[VN];
Edge E[EN];
void init(){
size = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v){
E[size].u = u;
E[size].v = v;
E[size].next = head[u];
head[u] = size++;
}
}g, g2; //g为原图, g2为新图
class Two_SAT{
public:
bool check(const Graph& g, const int n){
scc(g, 2*n);
for(int i=0; i<n; ++i)
if(belong[i] == belong[i+n])
return false;
return true;
}
void toposort(const Graph&g, Graph& g1, const int n){
g1.init();
memset(indeg, 0, sizeof(indeg));
for(int i=0; i<n; ++i){
opp[belong[i]] = belong[i+n];
opp[belong[i+n]] = belong[i];
}
for(int e=0; e<g.size; ++e){
int u = belong[g.E[e].u];
int v = belong[g.E[e].v];
if(u == v) continue;
++indeg[u];
g1.addEdge(v, u);
}
queue<int>que;
memset(color, WHITE, sizeof(color));
for(int i=1; i<=bcnt; ++i)
if(!indeg[i])
que.push(i);
int* head = g1.head;
Edge* E = g1.E;
while(!que.empty()){
int u = que.front();
que.pop();
if(color[u] != WHITE) continue;
color[u] = RED;
color[opp[u]] = BLUE;
for(int e=head[u]; e!=-1; e=E[e].next){
int v = E[e].v;
if(--indeg[v] == 0){
que.push(v);
}
}
}
for(int i=0; i<n; ++i){
if(color[belong[i]]==RED){
time_out(arr[i].t1, arr[i].d);
}else{
time_out(arr[i].t2-arr[i].d, arr[i].d);
}
}
}
private:
void tarjan(const Graph& g, const int u){
int v;
DFN[u] = low[u] = ++idx;
sta[top++] = u;
instack[u] = true;
for(int e=g.head[u]; e!=-1; e=g.E[e].next){
v = g.E[e].v;
if(DFN[v] == -1){
tarjan(g, v);
low[u] = min(low[u], low[v]);
}else if(instack[v]){
low[u] = min(low[u], DFN[v]);
}
}
if(DFN[u] == low[u]){
++bcnt;
do{
v = sta[--top];
instack[v] = false;
belong[v] = bcnt;
}while(u != v);
}
}
void scc(const Graph&g, const int n){
idx = top = bcnt = 0;
memset(DFN, -1, sizeof(DFN));
memset(instack, 0, sizeof(instack));
for(int i=0; i<n; ++i)
if(DFN[i] == -1)
tarjan(g, i);
}
private:
int idx, top, bcnt;
int DFN[VN];
int low[VN];
int belong[VN];
int sta[VN];
bool instack[VN];
// 求方案
int indeg[VN];
int color[VN];
int opp[VN];
}sat;
bool isCross(int a1, int b1, int a2, int b2){
return !(a2>=b1 || a1>=b2);
}
int main(){
int a, b;
while(~scanf("%d", &n)){
g.init();
for(int i=0; i<n; ++i){
scanf("%d:%d",&a, &b);
arr[i].t1 = a*60+b;
scanf("%d:%d",&a, &b);
arr[i].t2 = a*60+b;
scanf("%d", &arr[i].d);
}
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
const Couple& a=arr[i];
const Couple& b=arr[j];
if(isCross(a.t1, a.t1+a.d, b.t1, b.t1+b.d)){
g.addEdge(i, j+n);
g.addEdge(j, i+n);
}
if(isCross(a.t1, a.t1+a.d, b.t2-b.d, b.t2)){
g.addEdge(i, j);
g.addEdge(j, i+n);
}
if(isCross(a.t2-a.d, a.t2, b.t1, b.t1+b.d)){
g.addEdge(i+n, j+n);
g.addEdge(j, i);
}
if(isCross(a.t2-a.d, a.t2, b.t2-b.d, b.t2)){
g.addEdge(i+n, j);
g.addEdge(j+n, i);
}
}
}
if(!sat.check(g, n)){
puts("NO");
}else{
puts("YES");
sat.toposort(g,g2,n);
}
}
return 0;
}
分享到:
相关推荐
POJ水题集-----50道左右-----增加自信啊..
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
非常详细的ACM 搜索类型题 配套POJ练习,有详细思路
北大POJ1002-487-3279【Hash+Qsort】 解题报告+AC代码
很有用的解题报告。。是acm初级提高的必备资料。。。。。
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ2002-Squares 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码