POJ3683 Priest John's Busiest Day(神父约翰的忙日)题解(2-SAT及布尔方程运用)

挑战程序设计竞赛p326例题
poj3683
(奶牛呢）
如果你还不了解布尔方程和蕴含式，请先移步蕴含式是什么和布尔方程简介，运算法则
有些很巧妙的地方和技巧、想要总结一下。
首先这题我们考虑到，每个仪式可以在开始或结束时举行，可以用一个有补的变量表示；这时想到了布尔变量,对于一个仪式，我们用xi 表示它在刚开始时举行，若!xi 则表示它在结束时举行。

我们对于不同时发生的区间记为¬xi∨¬xj 为什么这样呢？请看下面的真值表

很明显，在不同时发生的仪式我们需要其中一个x 的值为false（即F）
而真值表证明了当且仅当两个仪式同时发生时，¬xi∨¬xj 为false
这表明我们可以用¬xi∨¬xj 的真假表示两个仪式是否同时发生。

这样我们可以根据各区间的起点和终点得出形如这样的布尔公式(xi∨xj)∧(¬xn∨¬xm)∧......使这个表达式值为真即可。

那么我们如何将这个表示为图呢？
根据公式a∨b≡¬a→b∧¬b→a
在求解和之积式的布尔方程[真值指派使整个方程为真]（《挑战》p324）的问题中，我们知道对于式a→b 可以形象表示为a到b的一条有向边，那么同样地在这个题中，我们把a∨b 表示为¬a→b∧¬b→a 后按此方式建边即可。

接下来是如何判断两仪式是否冲突的问题：
我们看到一个区间与另一个区间有交集，当且仅当两区间起点的最大值<终点最小值时成立，举例：区间[1,5] 显然与[2,4]和[2,7]有交集，而它们都满足两区间起点的最大值<终点最小值，举个不满足的例子：区间[1,3]与[4,6]就不满足，它们确实没有交集。
那么我们只需要这样去判断，再根据情况去加边就好了。比如，s[i]~(s[i]+d[i] )与(t[j]−d[j]) ~t[j]有冲突（即有交集），那么表示¬xi∨xj 为true，假定我们用0~n表示x1~xn, n+1~2*n表示¬x1到¬xn,即i→(j+n)∧(j+n)→(i+n),我们连边（i，j+n）和（j+n，i+n）。
这样再根据求布尔方程SAT问题的方法，我们就能解决这个题了。
代码

#include 
#include 
#include 
#include 
#include 
#include 
//AC
using namespace std;

const int maxn=2000;
int s[maxn];
int t[maxn];
int d[maxn];
bool used[maxn];
vector g[maxn];
vector rg[maxn];
vectorvs;
int rank[maxn];
int n;

void addedge(int from,int to)
{
    g[from].push_back(to);
    rg[to].push_back(from);
}

void dfs(int v)
{
    used[v]=true;
    for(unsigned i=0;imax(s[i],s[j]))
            {
                //!xiV!xj=xi->!xj ^ xj->!xi
                addedge(i,n+j);
                addedge(j,n+i);
            }
            if(min(s[i]+d[i],t[j])>max(s[i],t[j]-d[j]))
            {
                //!xiVxj
                addedge(i,j);
                addedge(n+j,n+i);
            }
            if(min(s[j]+d[j],t[i])>max(s[j],t[i]-d[i]))
            {
                //!xjVxi
                addedge(j,i);
                addedge(n+i,n+j);
            }
            if(min(t[i],t[j])>max(t[i]-d[i],t[j]-d[j]))
            {
                //xiVxj
                addedge(n+i,j);
                addedge(n+j,i);
            }
        }
    }

    memset(used,0,sizeof(used));
    vs.clear();
    for(int i=1;i<=n;i++)
    {
        if(!used[i])
        {
            dfs(i);
        }
    }

    int ruby=vs.size();
    memset(used,0,sizeof(used));
    int k=1;
    for(int i=ruby-1;i>=0;i--)
    {
        if(!used[vs[i]])
        {
            rdfs(vs[i],k);
            k++;
        }
    }
    k--;

    for(int i=1;i<=n;i++)
    {
        if(rank[i]==rank[i+n])
        {
            printf("NOn");
            return 0;
        }
    }
    printf("YESn");
    for(int i=1;i<=n;i++)
    {
        if(rank[i]>rank[n+i])
        {
            printf("%02d:%02d %02d:%02dn",s[i]/60,s[i]%60,(s[i]+d[i])/60,(s[i]+d[i])%60);
        }
        else
        {
            printf("%02d:%02d %02d:%02dn",(t[i]-d[i])/60,(t[i]-d[i])%60,t[i]/60,t[i]%60);
        }
    }
    return 0;
}

如果你不了解布尔方程，看不懂上面的式子，先看布尔方程的介绍及运算法则和蕴含式的计算，介绍
qwq谢谢看到这里。。。。