hdu1166敵兵布陣
線段樹的入門題,更新結(jié)點(diǎn)，查詢區(qū)間和
查看代碼
hdu1754 I Hate It
入門題，更新結(jié)點(diǎn)，查詢區(qū)間最大值
hdu 1698 Just a Hook
更新一段區(qū)間上的顏色，求值。學(xué)習(xí)了懶操作。
poj 2777 Count Color
給區(qū)間染色，求一段區(qū)間內(nèi)顏色的種樹。學(xué)會了線段樹的新寫法以及位操作。
hdu 3081 Marriage Match II
n男n女過家家，女生可以挑沒有跟她吵過架的男生匹配，也可與沒有跟她朋友吵過架的男生匹配（可以認(rèn)為是她喜歡的男生）。每輪游戲，每個女生選個她沒選過的男生，問游戲最多能進(jìn)行幾輪？
構(gòu)圖：先用并查集處理女生友情的傳遞。每個女向她喜歡的所有男生以及她朋友喜歡的男生連一條容量為1的邊。二分最大能進(jìn)行的輪數(shù)ans，源點(diǎn)向每個女生連一條容量為ans的邊，每個男生向匯點(diǎn)連一條容量為ans的邊。判斷最大流是否等于ans*N;
hdu 3277 Marriage Match III
同上，每個女生可以跟最多K個她不喜歡的男生匹配。
構(gòu)圖：每個女生拆為兩個點(diǎn)Gi1,Gi2。Gi1連一條容量為K的邊到Gi2。每個Gi2連一條容量為1的邊到女生i不喜歡的男生，源點(diǎn)連容量為ans的邊到每個Gi1。其余同上。
一開始用Dinic，無限TLE~~~ T_T 。萬般無奈下，只好上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)的最短路，對于邊如果起點(diǎn)到u的距離加終點(diǎn)到v的距離加這條邊的權(quán)值等于最短路長，那么在網(wǎng)絡(luò)流的圖中加一條u指向v，權(quán)值為1的邊。求起點(diǎn)到終點(diǎn)的最大流。
poj 3281 Dining
N頭牛，D種飲料，F(xiàn)種食物，每天牛吃一種食物一種飲料，食物和飲料都只有一份。問最大滿足多少頭牛。
構(gòu)圖：由于每頭牛只需一份飲料和食物，所以每頭牛要拆為兩點(diǎn)，連容量為1的邊。起點(diǎn)到所有食物連容量為1的邊，飲料到匯點(diǎn)連容量為1的邊。牛再和食物，飲料連。Dinic 0MS毫無壓力。
poj 2135 Farm Tour
求起點(diǎn)到終點(diǎn)再回起點(diǎn)的最短路徑。不能走重復(fù)的路。
構(gòu)圖：第一次寫費(fèi)用流。用的是樸素的spfa。費(fèi)用是距離。源點(diǎn)到1連一條容量為2的邊。終點(diǎn)到匯點(diǎn)連容量為2的邊。每條路徑的容量都為1.直接水過。
poj 2711 Leapin' Lizards
圖上有些柱子，開始時，一些蜥蜴在柱子上，當(dāng)蜥蜴跳離柱子時，柱子高度降1，蜥蜴不能跳到高度為0的柱子上，蜥蜴跳躍的距離為D，求有多少蜥蜴能夠跳出來。
構(gòu)圖：把每個有高度柱子拆為兩點(diǎn)，ai,bi，ai->bi容量為柱子高度。源點(diǎn)接到有蜥蜴的柱子ai上，能一步跳出去的柱子的bi接到匯點(diǎn)，容量INF，距離為D的任意兩格子都連容量INF的邊。求解最大流。求曼哈頓距離的時候出了點(diǎn)小問題，無限WA。注意輸出，單復(fù)數(shù)是不同的。
poj 2516 Minimum Cost
有N個客戶訂單，M座倉庫。給出訂單內(nèi)容和倉庫庫存，以及倉庫到客戶的費(fèi)用。求滿足所有客戶需求的最小費(fèi)用。
構(gòu)圖：原生態(tài)最小費(fèi)用流。每種商品都是獨(dú)立的，那么我們可以針對每種商品計(jì)算最小費(fèi)用。從源點(diǎn)連容量為倉庫i中k種商品庫存費(fèi)用為0的邊到倉庫i,倉庫i接容量為無限，費(fèi)用為到客戶j的費(fèi)用。如果最大流等于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)連邊。感覺復(fù)雜度過不了，膜拜了傳說中神一般的構(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)。
割點(diǎn)
割點(diǎn)：如果在圖G中刪去一個結(jié)點(diǎn)u后，圖G的連通分枝數(shù)增加，即W(G-u)>W(G)，則稱結(jié)點(diǎn)u為G的割點(diǎn)，又稱關(guān)節(jié)點(diǎn)。
直觀地說，就是刪除了連通圖的某點(diǎn)后，圖不在連通，而是分為幾個連通分量。
性質(zhì)：（1）考慮根節(jié)點(diǎn)Root，如果Root有數(shù)量多于1的子結(jié)點(diǎn)時，Root是割點(diǎn)。
（2）考慮非根結(jié)點(diǎn)u，當(dāng)且僅當(dāng)u的某個兒子及兒子的子孫均沒有指向u的祖先的后向邊時，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ì): 對于一條邊<u,v>，v是u的孩子如果兒子及兒子的子孫均沒有指向u的祖先的后向邊時，<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的講解，很精彩
推薦閱讀：
lrj的黑書P285
由于原來的yo2不能用了，只好轉(zhuǎn)戰(zhàn)CPP。這個Blog將會用來記錄一些胡思亂想的成果，神經(jīng)質(zhì)的言語。
形式主義的來個HelloWorld:
1
cout<<"Hello World"<<endl;