1.有一張無向圖，現(xiàn)在要給每個(gè)點(diǎn)染上黑色或白色，最后每個(gè)點(diǎn)的染色代價(jià)是它與離這個(gè)點(diǎn)最近的不同色節(jié)點(diǎn)的距離。求最小代價(jià)。所有邊權(quán)$\geq 0$且互不相同。

分三種情況：

兩點(diǎn)都染了色：兩點(diǎn)都跟其它點(diǎn)算過最小距離了，不用管。

一點(diǎn)染了色：相當(dāng)于擴(kuò)展連通塊，染了色的點(diǎn)向沒染色的點(diǎn)擴(kuò)展染色，顏色相同。

兩點(diǎn)都沒染色：兩點(diǎn)直接相連（且邊長是最短距離）。

?

2.題目大意同上，求得到最小代價(jià)的方案數(shù)。

0的邊兩邊的點(diǎn)有多少個(gè)子樹，方案數(shù)就累加上2的多少次方。

?

?

3.一張無向圖，給每條邊染兩種顏色之一，使每個(gè)度大于等于2的點(diǎn)都連接兩種顏色的邊。問能否做到。Yes或No。

首先光禿禿的偶環(huán)（奇數(shù)條邊）肯定無解（發(fā)芽就有解了），光禿禿的奇環(huán)（偶數(shù)條邊）肯定有解（不知道這個(gè)結(jié)論的可以跳過這題了）。

環(huán)？想到了樹。

可以先把這張圖取出$n-1$條邊，讓整張圖構(gòu)成一棵樹，

我們知道，樹中只有三種邊：樹邊（圖中黑邊）、回邊（返祖邊）（圖中紅邊）、跨邊（有向圖特有）。

對(duì)于樹上任意的度$\ge 2$ 的點(diǎn)，它的兩邊染上不同的顏色即可，如果再有一條返祖邊連向它，這條新邊染什么顏色都可以，必定能滿足另一頭的要求。

但對(duì)于度為 $1$ 的點(diǎn)呢？根和葉子結(jié)點(diǎn)都是度為1的點(diǎn)，這時(shí)候我們就要跑這個(gè)環(huán)。

只有這個(gè)環(huán)本身（即不算發(fā)芽）有偶數(shù)個(gè)點(diǎn)且發(fā)芽的情況需要我們考慮是否有解。

其實(shí)這就是偶環(huán)上發(fā)芽的情況。如圖

那么發(fā)芽點(diǎn)在原環(huán)上的兩條相鄰邊就可以染成同色，然后把另一種顏色染到芽上。

但如果發(fā)的芽下面也有邊連向了入讀為1的邊呢？

如果新連出來的環(huán)還是偶環(huán)，好像依然不可行。

?

那什么情況下可行？如下。

只要偶環(huán)與奇環(huán)相套，至少就可以從發(fā)芽點(diǎn)把另一種顏色沿著芽流出去了。

結(jié)合這么一個(gè)知識(shí)：偶環(huán)套偶環(huán)=偶環(huán)

可得：只有整張圖只要存在純偶環(huán)（就是不與奇環(huán)相套的偶環(huán)）就無解，否則有解。

所以這是個(gè)結(jié)論題，以上都是推導(dǎo)，并非題解。

題解的話就再扯點(diǎn)沒用的（找純偶環(huán)的方法）：去掉奇度點(diǎn)（它們是整張圖的芽，處于被動(dòng)染色狀態(tài)，環(huán)上芽才是主動(dòng)），把圖的剩余部分做Tarjan求無向圖強(qiáng)連通分量（MD準(zhǔn)確地說是邊雙連通分量）。在每一個(gè)分量中任選一個(gè)起點(diǎn)，看是否存在經(jīng)過偶數(shù)條邊回到起點(diǎn)的方案。如果存在，說明存在奇環(huán)，這個(gè)強(qiáng)連通分量滿足條件。如果所有的強(qiáng)連通分量都滿足條件，說明圖中不存在純偶環(huán)，有解。否則存在純偶環(huán)，無解。

?

4.有向圖，邊權(quán)只有0和1，求單源最短路。（線性算法）

我們都知道，廣搜時(shí)總是取出隊(duì)列中的第一個(gè)數(shù)。求最短路情況下，為了讓更新盡量有意義，我們當(dāng)然希望先從隊(duì)列中取出（目前更新的）到起點(diǎn)距離盡量小的，這樣可以盡量多地更新它周圍點(diǎn)的最短路。

然后這題邊權(quán)只有0和1，我們甚至不用寫單調(diào)隊(duì)列，如果按照上述貪心取法，我們發(fā)現(xiàn)廣搜隊(duì)列中 前面一段的距離值 與 后面一段的距離值 的差值不超過1。

為什么呢？

因?yàn)槲覀円〕龅狡瘘c(diǎn)距離盡量小的，所以總是會(huì)取距離值相對(duì)較小的。并且更新時(shí)邊權(quán)只會(huì)是0或1。

結(jié)合數(shù)學(xué)歸納法可知，

一開始隊(duì)列中只有起點(diǎn)，距離為0，隊(duì)列中距離值的差為0。

然后更新了周圍的點(diǎn)，有些點(diǎn)的距離值更新為0，有些點(diǎn)的距離值更新為1。

然后我們一直更新 距離值為0的點(diǎn) 的周圍的點(diǎn)，直到隊(duì)列中所有點(diǎn)的距離值都為1。

此時(shí)已經(jīng)不存在未被更新過的到起點(diǎn)距離為0的點(diǎn)了（廣搜常識(shí)）。

此時(shí)隊(duì)列中所有點(diǎn)的距離值是1。

然后把1當(dāng)成之前的0，接下來更新出的距離值2當(dāng)成之前的1，就歸納為一樣的步驟了。

由此證明這樣做的廣搜隊(duì)列中 前面一段的距離值 與 后面一段的距離值 的差值不超過1。

然后邊權(quán)還只有0和1，隊(duì)列操作比較簡(jiǎn)單，把通過權(quán)值為0更新的點(diǎn)接到隊(duì)頭，通過權(quán)值為1更新的點(diǎn)放到隊(duì)尾即可。隊(duì)頭的點(diǎn)的距離值就是相對(duì)較小的。

?

拓展：有向圖，邊權(quán)只有0~20，求單源最短路。

把隊(duì)列分割成21個(gè)桶，每個(gè)桶依次存$x,x+1,...,x+20$這21個(gè)距離值。廣搜時(shí)不停取第一個(gè)桶中的點(diǎn)，把被該點(diǎn)更新距離的點(diǎn) 放到對(duì)應(yīng)距離值的桶里。如果第一個(gè)桶中沒有點(diǎn)，就把所有桶存放的距離值上調(diào)至使第一個(gè)桶中有點(diǎn)。

易證點(diǎn)肯定有桶放。

?

5.每個(gè)點(diǎn)有一個(gè)（開采礦物的）費(fèi)用，邊權(quán)依然只有0和1，求分別開采每個(gè)點(diǎn)的礦物時(shí)的最小費(fèi)用。

?

6.執(zhí)行k個(gè)操作，每個(gè)操作連接兩個(gè)點(diǎn)，問每個(gè)操作后圖中有多少條割邊。（LCT會(huì)超時(shí)）

邊雙連通（環(huán)）的情況下給圖縮點(diǎn)，這個(gè)圖會(huì)變成一個(gè)森林。森林之間的每條邊都是一條割邊。因此用兩個(gè)并查集維護(hù)，一個(gè)維護(hù)每個(gè)連通塊的點(diǎn)，另一個(gè)維護(hù)每個(gè)邊雙連通塊的點(diǎn)。

轉(zhuǎn)載于:https://www.cnblogs.com/scx2015noip-as-php/p/9737138.html

總結(jié)

以上是生活随笔為你收集整理的【2018.10.2】Note of CXM的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。