構(gòu)圖：先用并查集處理女生友情的傳遞。每個(gè)女向她喜歡的所有男生以及她朋友喜歡的男生連一條容量為1的邊。二分最大能進(jìn)行的輪數(shù)ans，源點(diǎn)向每個(gè)女生連一條容量為ans的邊，每個(gè)男生向匯點(diǎn)連一條容量為ans的邊。判斷最大流是否等于ans*N;

hdu 3277 Marriage Match III

同上，每個(gè)女生可以跟最多K個(gè)她不喜歡的男生匹配。

構(gòu)圖：每個(gè)女生拆為兩個(gè)點(diǎn)Gi1,Gi2。Gi1連一條容量為K的邊到Gi2。每個(gè)Gi2連一條容量為1的邊到女生i不喜歡的男生，源點(diǎn)連容量為ans的邊到每個(gè)Gi1。其余同上。

一開(kāi)始用Dinic，無(wú)限TLE~~~ T_T 。萬(wàn)般無(wú)奈下，只好上Qinz大牛的博客膜拜了ISAP的模板，再結(jié)合網(wǎng)上各路神牛的論文，終于得出了一份自己的ISAP模板～，提交果斷AC～

hdu 3416 Marriage Match IV

有向圖，求起點(diǎn)到終點(diǎn)的最短路的條數(shù)。

構(gòu)圖：求最短路，起點(diǎn)到所有點(diǎn)的最短路，所有邊反向，求終點(diǎn)到所有點(diǎn)的最短路，對(duì)于邊如果起點(diǎn)到u的距離加終點(diǎn)到v的距離加這條邊的權(quán)值等于最短路長(zhǎng)，那么在網(wǎng)絡(luò)流的圖中加一條u指向v，權(quán)值為1的邊。求起點(diǎn)到終點(diǎn)的最大流。

poj 3281 Dining

N頭牛，D種飲料，F(xiàn)種食物，每天牛吃一種食物一種飲料，食物和飲料都只有一份。問(wèn)最大滿足多少頭牛。

構(gòu)圖：由于每頭牛只需一份飲料和食物，所以每頭牛要拆為兩點(diǎn)，連容量為1的邊。起點(diǎn)到所有食物連容量為1的邊，飲料到匯點(diǎn)連容量為1的邊。牛再和食物，飲料連。Dinic 0MS毫無(wú)壓力。

poj 2135 Farm Tour

求起點(diǎn)到終點(diǎn)再回起點(diǎn)的最短路徑。不能走重復(fù)的路。

構(gòu)圖：第一次寫(xiě)費(fèi)用流。用的是樸素的spfa。費(fèi)用是距離。源點(diǎn)到1連一條容量為2的邊。終點(diǎn)到匯點(diǎn)連容量為2的邊。每條路徑的容量都為1.直接水過(guò)。

poj 2711 Leapin' Lizards

圖上有些柱子，開(kāi)始時(shí)，一些蜥蜴在柱子上，當(dāng)蜥蜴跳離柱子時(shí)，柱子高度降1，蜥蜴不能跳到高度為0的柱子上，蜥蜴跳躍的距離為D，求有多少蜥蜴能夠跳出來(lái)。

構(gòu)圖：把每個(gè)有高度柱子拆為兩點(diǎn)，ai,bi，ai->bi容量為柱子高度。源點(diǎn)接到有蜥蜴的柱子ai上，能一步跳出去的柱子的bi接到匯點(diǎn)，容量INF，距離為D的任意兩格子都連容量INF的邊。求解最大流。求曼哈頓距離的時(shí)候出了點(diǎn)小問(wèn)題，無(wú)限WA。注意輸出，單復(fù)數(shù)是不同的。

poj 2516 Minimum Cost

有N個(gè)客戶訂單，M座倉(cāng)庫(kù)。給出訂單內(nèi)容和倉(cāng)庫(kù)庫(kù)存，以及倉(cāng)庫(kù)到客戶的費(fèi)用。求滿足所有客戶需求的最小費(fèi)用。

構(gòu)圖：原生態(tài)最小費(fèi)用流。每種商品都是獨(dú)立的，那么我們可以針對(duì)每種商品計(jì)算最小費(fèi)用。從源點(diǎn)連容量為倉(cāng)庫(kù)i中k種商品庫(kù)存費(fèi)用為0的邊到倉(cāng)庫(kù)i,倉(cāng)庫(kù)i接容量為無(wú)限，費(fèi)用為到客戶j的費(fèi)用。如果最大流等于k的需求總量那么k就滿足了。可以記錄每種商品需求總量和庫(kù)存總量。供不應(yīng)求則輸出-1 。

poj 3680 Intervals

已知N條線段的端點(diǎn)和線段的權(quán)值，選一些線段使權(quán)值最大，坐標(biāo)軸上一點(diǎn)最多被覆蓋K次。

構(gòu)圖：費(fèi)用流。原打算拆點(diǎn)連邊。感覺(jué)復(fù)雜度過(guò)不了，膜拜了傳說(shuō)中神一般的構(gòu)圖：先把點(diǎn)離散化，起點(diǎn)到第一點(diǎn)連權(quán)值為0，容量為K，i到i+1連權(quán)值為0容量為K的邊，直到匯點(diǎn)。一條線段的起始點(diǎn)連一條容量為1權(quán)值為-w的邊到結(jié)束點(diǎn)。

posted @ 2010-09-09 17:03 ZAKIR 閱讀(356) | 評(píng)論 (0) | 編輯收藏

2010年8月30日

圖的割點(diǎn)與割邊學(xué)習(xí)筆記

割點(diǎn)

割點(diǎn)：如果在圖G中刪去一個(gè)結(jié)點(diǎn)u后，圖G的連通分枝數(shù)增加，即W(G-u)>W(G)，則稱結(jié)點(diǎn)u為G的割點(diǎn)，又稱關(guān)節(jié)點(diǎn)。
直觀地說(shuō)，就是刪除了連通圖的某點(diǎn)后，圖不在連通，而是分為幾個(gè)連通分量。

性質(zhì)：（1）考慮根節(jié)點(diǎn)Root，如果Root有數(shù)量多于1的子結(jié)點(diǎn)時(shí)，Root是割點(diǎn)。

（2）考慮非根結(jié)點(diǎn)u，當(dāng)且僅當(dāng)u的某個(gè)兒子及兒子的子孫均沒(méi)有指向u的祖先的后向邊時(shí)，u是割點(diǎn)。（LOW[v]>=DFN[u],v是u的孩子）

代碼：

1 void DFS(int cur,int par)
2 {
3     dfn[cur]=low[cur]=++Index;
4
5     int size=adj[cur].size();
6     int cnt=0;
7     for(int i=0;i<size;i++)
8     {
9         int v=adj[cur][i];
10         if(!dfn[v])
11         {
12             cnt++;
13             DFS(v,cur);
14             if(low[cur]>low[v])
15                 low[cur]=low[v];
16             if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur]))
17                 flag[cur]=true;
18         }
19         else if(v!=par&&low[cur]>dfn[v])
20             low[cur]=dfn[v];
21     }
22 }
23

割邊

割邊：如果在圖G中刪去一條邊e后，圖G的連通分支數(shù)增加，即W(G-e)>W(G)，則稱邊u為G的橋，又稱割邊或關(guān)節(jié)邊。

性質(zhì): 對(duì)于一條邊<u,v>，v是u的孩子如果兒子及兒子的子孫均沒(méi)有指向u的祖先的后向邊時(shí)，<u,v>是割邊。（LOW[v]>DFN[u]）

代碼：

1 void CutEdge(int cur,int par)
2 {    dfn[cur]=low[cur]=++Index;
3
4     for(int i=head[cur];i;i=buf[i].next)
5     {
6         int v=buf[i].v;
7         if(v==par)continue;
8         if(!dfn[v])
9         {
10             CutEdge(v,cur);
11             if(low[cur]>low[v])
12                 low[cur]=low[v];
13             if(low[v]>dfn[cur])
14             {
15                     ans[nAns++]=buf[i].id;
16             }
17         }
18         else if(low[cur]>dfn[v])
19             low[cur]=dfn[v];
20     }
21 }

相關(guān)習(xí)題：

POJ 1144 Network 赤果果的求割點(diǎn)的題。

相關(guān)鏈接:
Beyond the Void的講解，很精彩