挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽p326例題
poj3683
(奶牛呢）
如果你還不了解布爾方程和蘊(yùn)含式，請(qǐng)先移步蘊(yùn)含式是什么和布爾方程簡(jiǎn)介，運(yùn)算法則
有些很巧妙的地方和技巧、想要總結(jié)一下。
首先這題我們考慮到，每個(gè)儀式可以在開(kāi)始或結(jié)束時(shí)舉行，可以用一個(gè)有補(bǔ)的變量表示；這時(shí)想到了布爾變量,對(duì)于一個(gè)儀式，我們用xi 表示它在剛開(kāi)始時(shí)舉行，若!xi 則表示它在結(jié)束時(shí)舉行。

我們對(duì)于不同時(shí)發(fā)生的區(qū)間記為?xi∨?xj 為什么這樣呢？請(qǐng)看下面的真值表

很明顯，在不同時(shí)發(fā)生的儀式我們需要其中一個(gè)x 的值為false（即F）
而真值表證明了當(dāng)且僅當(dāng)兩個(gè)儀式同時(shí)發(fā)生時(shí)，?xi∨?xj 為false
這表明我們可以用?xi∨?xj 的真假表示兩個(gè)儀式是否同時(shí)發(fā)生。

這樣我們可以根據(jù)各區(qū)間的起點(diǎn)和終點(diǎn)得出形如這樣的布爾公式(xi∨xj)∧(?xn∨?xm)∧......使這個(gè)表達(dá)式值為真即可。

那么我們?nèi)绾螌⑦@個(gè)表示為圖呢？
根據(jù)公式a∨b≡?a→b∧?b→a
在求解和之積式的布爾方程[真值指派使整個(gè)方程為真]（《挑戰(zhàn)》p324）的問(wèn)題中，我們知道對(duì)于式a→b 可以形象表示為a到b的一條有向邊，那么同樣地在這個(gè)題中，我們把a∨b 表示為?a→b∧?b→a 后按此方式建邊即可。

接下來(lái)是如何判斷兩儀式是否沖突的問(wèn)題：
我們看到一個(gè)區(qū)間與另一個(gè)區(qū)間有交集，當(dāng)且僅當(dāng)兩區(qū)間起點(diǎn)的最大值<終點(diǎn)最小值時(shí)成立，舉例：區(qū)間[1,5] 顯然與[2,4]和[2,7]有交集，而它們都滿足兩區(qū)間起點(diǎn)的最大值<終點(diǎn)最小值，舉個(gè)不滿足的例子：區(qū)間[1,3]與[4,6]就不滿足，它們確實(shí)沒(méi)有交集。
那么我們只需要這樣去判斷，再根據(jù)情況去加邊就好了。比如，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）。
這樣再根據(jù)求布爾方程SAT問(wèn)題的方法，我們就能解決這個(gè)題了。
代碼

#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;
}

如果你不了解布爾方程，看不懂上面的式子，先看布爾方程的介紹及運(yùn)算法則和蘊(yùn)含式的計(jì)算，介紹
qwq謝謝看到這里。。。。