]]>
hdu1754 I Hate It
入門題，更新結(jié)點，查詢區(qū)間最大值
hdu 1698 Just a Hook
更新一段區(qū)間上的顏色，求值。學習了懶操作。
poj 2777 Count Color
給區(qū)間染色，求一段區(qū)間內(nèi)顏色的種樹。學會了線段樹的新寫法以及位操作。
]]>
n男n女過家家，女生可以挑沒有跟她吵過架的男生匹配，也可與沒有跟她朋友吵過架的男生匹配（可以認為是她喜歡的男生）。每輪游戲，每個女生選個她沒選過的男生，問游戲最多能進行幾輪？
構(gòu)圖：先用并查集處理女生友情的傳遞。每個女向她喜歡的所有男生以及她朋友喜歡的男生連一條容量為1的邊。二分最大能進行的輪數(shù)ans，源點向每個女生連一條容量為ans的邊，每個男生向匯點連一條容量為ans的邊。判斷最大流是否等于ans*N;
hdu 3277 Marriage Match III
同上，每個女生可以跟最多K個她不喜歡的男生匹配。
構(gòu)圖：每個女生拆為兩個點Gi1,Gi2。Gi1連一條容量為K的邊到Gi2。每個Gi2連一條容量為1的邊到女生i不喜歡的男生，源點連容量為ans的邊到每個Gi1。其余同上。
一開始用Dinic，無限TLE~~~ T_T 。萬般無奈下，只好上Qinz大牛的博客膜拜了ISAP的模板，再結(jié)合網(wǎng)上各路神牛的論文，終于得出了一份自己的ISAP模板～，提交果斷AC～
hdu 3416 Marriage Match IV
構(gòu)圖：求最短路，起點到所有點的最短路，所有邊反向，求終點到所有點的最短路，對于邊
]]>
割點：如果在圖G中刪去一個結(jié)點u后，圖G的連通分枝數(shù)增加，即W(G-u)>W(G)，則稱結(jié)點u為G的割點，又稱關(guān)節(jié)點。
直觀地說，就是刪除了連通圖的某點后，圖不在連通，而是分為幾個連通分量。
性質(zhì)：（1）考慮根節(jié)點Root，如果Root有數(shù)量多于1的子結(jié)點時，Root是割點。
（2）考慮非根結(jié)點u，當且僅當u的某個兒子及兒子的子孫均沒有指向u的祖先的后向邊時，u是割點。（LOW[v]>=DFN[u],v是u的孩子）
代碼：
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]）
代碼：
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)習題：
POJ 1144 Network 赤果果的求割點的題。
相關(guān)鏈接:
Beyond the Void的講解，很精彩
推薦閱讀：
lrj的黑書P285
]]>
cout<<"Hello World"<<endl;]]>