圖論算法初步

1、圖論算法初步泰安一中馬玉坤最短路問題NOI2010 社交網絡SRM626 D1 Medium 題意：給定一個有向圖，邊權非負。你要從s出發(fā)，最終到達t，每經過一條邊時，你可以消耗一點魔法值，使這條邊的權值暫時取反（“暫時”是指當你走過這條邊之后，這條邊的權值就會還原）。給定初始魔法值，求最短路徑長度。 N=50,M=2500,初始魔法值c=1e9 先考慮c較小的情況 c較大的情況int calc(int i,int j,int c) if(c%2=1) FOR(k,m)distijc=min(distijc,distiukc/2-wk+distvkjc/2); else FOR(k,n)dis

2、tijc=min(distijc,distikc/2+distkjc/2);SDOI2009 Elaxia的路線 題意：求正邊權無向圖中，兩對點間(S1,T1),(S2,T2)最短路的最長公共路徑。 N=1500 Key：最優(yōu)答案一定是連續(xù)的一條路徑，所以先求出哪些邊在最短路網（由所有滿足dist(S,ui)+wi+dist(vi,T) = dist(S,T) 的邊(ui,vi,wi)組成的圖）中，然后dp差分約束墨墨的等式生成樹問題最小極差生成樹，最優(yōu)比率生成樹NOIP2013貨車運輸 給定無向圖G，Q次詢問，每次詢問求出一條從S到T的路徑，使得這條路徑上的最小邊權最大。 N10000,M5

3、0000,Q30000 先思考暴力貪心做法 是不是跟kruskal很像？ 答案一定是最大生成樹上S到T的路徑 需要離線tarjan或HLD或倍增用求lca的方式求兩點樹上路徑最小邊權BJOI2010 次小生成樹 給定一個無向圖，求這個圖的嚴格次小（也就是不能等于）生成樹。 N=100000,M=300000 首先，次小生成樹一定跟最小生成樹只差一條邊 枚舉不在最小生成樹上的邊(ui,vi,wi)，如果要把這條邊加入最小生成樹，顯然需要刪除最小生成樹上ui到vi路徑中 的一條邊，所以只需要求一下最小生成樹上ui到vi 的路徑上的最大邊權和嚴格次大邊權就可以。強連通分量(SCC)先求出強連通分量，

4、然后縮點。USACO 2003 Fall Popular Cows 給定一個有向圖，求出那些點滿足：從其他任意點出發(fā)，都能抵達這個點。 N=10000,M=50000 先求出強連通分量，然后縮點。如果圖不連通或有多于一個強連通分量出度為0，答案為0；否則出度為0的強連通分量內的點數即為答案。中山市選2011 殺人游戲 一位冷血的殺手潛入 Na-wiat，并假裝成平民。警察希望能在 N 個人里面，查出誰是殺手。 警察能夠對每一個人進行查證，假如查證的對象是平民，他會告訴警察，他認識的人， 誰是殺手， 誰是平民。 假如查證的對象是殺手， 殺手將會把警察干掉。 現在警察掌握了每一個人認識誰。 每個人

5、是殺手的概率是相同的。根據最優(yōu)的情況，保證警察自身安全并知道誰是殺手的概率最大是多少？ N=100000,M=300000 先求出強連通分量，然后縮點。之后就可以發(fā)現對于警察，最優(yōu)策略是詢問先入度為零的強連通分量，之后不需要擔一點風險就能找到殺手。（需要注意一些特殊情況。）NOIP2009 最優(yōu)貿易 給定有向圖，每個點i都有點權ai，求maxav-au|點1能到點u 且 點u能到點v 且 點v能到點n N=100000,M=500000 先求出強連通分量，然后縮點。對于每個點1所能到達的強連通分量（設這個SCC編號為i），我們都可以dp求出這個SCC中的點到點n所有路徑中的最大點權（設為dpi

6、），然后用dpi-minai （minai表示強連通分量i內最大的點權）更新答案。 方程:dpi=maxdpj | i連向j且j能到達點n所在SCC 吐槽一下CCF的數據，50分算法能得100分。二分圖問題SAM 在N*M的網格中，有若干個打擊目標，一次打擊可以將一行或一列的目標全部消滅。求最小打擊次數，使得全部目標被消滅。 N,M=100 如果(i,j)有目標，左i向右j連一條邊，求最大流，設最大流為f。顯然消滅這些目標至少需要f次打擊，且f次打擊可以消滅所有目標。 最小點覆蓋SRM594 D1 Medium 給定一個n*m的圍棋棋盤，有些棋盤格子是空的，有些格子上有黑棋或白棋，而且沒有兩個白棋相鄰?，F在，你可以