本文共 1555 字，大约阅读时间需要 5 分钟。

【题目链接】

【题目大意】

有个小镇上有n对夫妻要举办婚礼，每队夫妻都要请镇上的牧师举行一个仪式，但是镇上只有一个牧师，牧师一次只能为一对夫妻做仪式。

已知每队夫妻的婚礼的起始t1和结束的时间t2， 他们举办仪式的时间是d，仪式只能在婚礼开始的前d时间举行或者在结束之前的d内举行。问牧师能不能合理安排，使得每对夫妻都能举办仪式？

【思路】

对于每一对夫妻，他们要么在开始时做仪式，要么在结束时做仪式，所以是2-SAT模型。

这题要输出任一个方案，研究了好几个小时。。。

【代码】

#include
   
     #include
    
     #include
     
      #include
      
       #include
       
        #define WHITE -1#define RED 1#define BLUE 0using 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