poj - 3683 - Priest John's Busiest Day（2-SAT）

题意：有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。。。

#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\n", (T[id]-D[id])/60, (T[id]-D[id])%60, T[id]/60, T[id]%60);  
                else printf("%02d:%02d %02d:%02d\n", 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;  
}

补充：软件开发 , C++ ,