poj - 3683 - Priest John's Busiest Day(2-SAT)
3447 ワード
标题:N回の結婚式があり、それぞれの結婚式の開始時間はSiで、終了時間はTiで、それぞれの結婚式には儀式があり、Diを経て、この儀式はSiの時点で始まるか、Ti-Diの時点で始まるか、それぞれの結婚式の儀式の時間を手配して、司会者のJohnがすべての儀式の全過程に参加できるかどうかを聞く.
タイトルリンク:http://poj.org/problem?id=3683
-->>各結婚式の儀式は、開始段で行われるか、終了段で行われるか、必ず行われ、各結婚式に衝突がないことを要求します-->>2-SAT..
2-SATはとても神妙で、このような问题に対して、手が届いて捕まえたと言える.の
LJ『トレーニングガイド』の書き方がわかりやすいです..そこで使いました...(2003年の伍旭論文のO(n)のアルゴリズムに比べて、時間的には「訓練ガイド」の書き方は及ばない).
2-SATにとって、建図は非常に重要です...
-->>結婚式をiとし、mark[2*i]==1はその開始段で式を行い、mark[2*i+1]==1はその終了段で式を行う.
建図構想:一つの儀式iと別の儀式jに対して、iとjが衝突すれば、iが開催できないかjが開催できないことを説明する.のすなわちi==0||j==0であるため、i'->j,j'->iとなる.
タイトルリンク:http://poj.org/problem?id=3683
-->>各結婚式の儀式は、開始段で行われるか、終了段で行われるか、必ず行われ、各結婚式に衝突がないことを要求します-->>2-SAT..
2-SATはとても神妙で、このような问题に対して、手が届いて捕まえたと言える.の
LJ『トレーニングガイド』の書き方がわかりやすいです..そこで使いました...(2003年の伍旭論文のO(n)のアルゴリズムに比べて、時間的には「訓練ガイド」の書き方は及ばない).
2-SATにとって、建図は非常に重要です...
-->>結婚式をiとし、mark[2*i]==1はその開始段で式を行い、mark[2*i+1]==1はその終了段で式を行う.
建図構想:一つの儀式iと別の儀式jに対して、iとjが衝突すれば、iが開催できないかjが開催できないことを説明する.のすなわちi==0||j==0であるため、i'->j,j'->iとなる.
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 1000 + 10;
int N;
int S[maxn], S1[maxn], S2[maxn], T[maxn], T1[maxn], T2[maxn], D[maxn];
int t[maxn][2];
struct Twoset {
int n;
vector<int> G[maxn*2];
bool mark[maxn*2];
int stk[maxn*2], c;
void init(int n) {
this->n = n;
for(int i = 0; i < 2*n; i++) G[i].clear();
memset(mark, 0, sizeof(mark));
}
void add_clause(int x, int xval, int y, int yval) {
x = x * 2 + xval;
y = y * 2 + yval;
G[x^1].push_back(y);
G[y^1].push_back(x);
}
bool dfs(int x) {
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x] = true;
stk[++c] = x;
int sz = G[x].size();
for(int i = 0; i < sz; i++) {
int v = G[x][i];
if(!dfs(v)) return false;
}
return true;
}
bool YES() {
for(int i = 0; i < 2*n; i += 2) if(!mark[i] && !mark[i+1]) {
c = 0;
if(!dfs(i)) {
while(c) mark[stk[c--]] = false;
if(!dfs(i+1)) return false;
}
}
return true;
}
void solve() {
if(YES()) {
puts("YES");
for(int i = 0; i < 2*n; i++) if(mark[i]) {
int id = i / 2;
if(i&1) printf("%02d:%02d %02d:%02d
", (T[id]-D[id])/60, (T[id]-D[id])%60, T[id]/60, T[id]%60);
else printf("%02d:%02d %02d:%02d
", S[id]/60, S[id]%60, (S[id]+D[id])/60, (S[id]+D[id])%60);
}
}
else puts("NO");
}
} solver;
bool isok(int L1, int R1, int L2, int R2) { //
return R1 <= L2 || R2 <= L1;
}
void read() {
for(int i = 0; i < N; i++) {
scanf("%d:%d %d:%d %d", &S1[i], &S2[i], &T1[i], &T2[i], &D[i]);
S[i] = S1[i] * 60 + S2[i];
T[i] = T1[i] * 60 + T2[i];
t[i][0] = S[i];
t[i][1] = T[i] - D[i];
}
}
void build() {
for(int i = 0; i < N; i++) for(int a = 0; a < 2; a++)
for(int j = i+1; j < N; j++) for(int b = 0; b < 2; b++)
if(!isok(t[i][a], t[i][a]+D[i], t[j][b], t[j][b]+D[j])) // , a,b, a^1 b^1
solver.add_clause(i, a^1, j, b^1);
}
int main()
{
while(scanf("%d", &N) == 1) {
solver.init(N);
read();
build();
solver.solve();
}
return 0;
}