模板專區(qū)別人的幾乎全

1、1ACM 常用模板1圖論31.11.21.3術(shù)語3集、覆蓋集、支配集之間關(guān)系3DFS41.3.11.3.21.3.3割頂6橋7強連通分量71.41.51.61.71.81.91.101.11最小點基7拓?fù)渑判?歐拉路8哈密頓路（正確？）9Bellman-ford9差分約束系統(tǒng)（用 bellman-ford 解）10dag 最短路徑10二分圖匹配111.11.11.11.2匈牙利算法11KM 算法121.12網(wǎng)絡(luò)流151.12.11.12.21.12.31.12.41.12.5最大流15上下界的網(wǎng)絡(luò)的最大流17上下界的網(wǎng)絡(luò)的最小流17最小費用最大流18上下界的網(wǎng)絡(luò)的最小費用最小流212數(shù)論212

2、.12.22.32.42.52.62.72.82.92.102.112.122.13最大公約數(shù).21最小公倍數(shù) lcm22快速冪取模 BLmodP(O(logb)22Fermat 小定理22Rabin-Miller 偽素數(shù)測試22Pollard-rho22擴(kuò)展歐幾里德算法 extended-.24歐拉定理24線性同余方程 axb(mod n)24中國剩余定理25Discrete Logging(BL = N (mod P)26N!最后一個不為 0 的數(shù)字27214 以內(nèi)的素數(shù)273數(shù)據(jù)結(jié)構(gòu)313.1堆（最小堆）313.1.13.1.23.1.3刪除最小值元素：31元素和向上調(diào)整：32堆的建立3

3、23.23.3并查集32樹狀數(shù)組342ACM 常用模板3.3.13.3.23.3.33.3.4LOWBIT34修改 ap34前綴和 A1+Ap34一個二維樹狀數(shù)組的程序353.4 線段樹363.5 字符串383.5.13.5.2字符串哈希38KMP 算法404計算幾何424.14.24.34.44.54.64.74.8直線交點42線段相交42三點外接圓圓心43點在多邊形內(nèi)43兩圓交面積44最小包圍圓44坐標(biāo)46凸包475Problem495.1RMQ-LCA495.1.15.1.25.1.35.1.45.1.55.1.6Range Minimum Query(RMQ)49Lowest Comm

4、on Ancestor (LCA)53Reduction from LCA to RMQ56From RMQ to LCA58An<O(N), O(1)> algorithm for the restricted RMQ61An AC programme625.25.3最長公共子序列 LCS65最長上升子序列/最長不下降子序列(LIS)665.3.15.3.2O(n2)66O(nlogn)675.45.5Joseph 問題680/1 背包問題696組合數(shù)學(xué)相關(guān)706.16.26.3The Number of the Same BST70排列生成72逆序736.3.1歸并排序求逆序7

5、37數(shù)值分析737.17.27.37.47.5二分法73迭代法(x=f(x)74牛頓迭代75數(shù)值75高斯消元768其它783ACM 常用模板1圖論1.1術(shù)語支配集：D 是圖 G 的一個頂點子集，對于 G 的任一頂點 U，要么 U 是D 集合的一個頂點元素，要么與 D 中的一個頂點相鄰，那么 D 稱為圖G 的一個支配集。極小支配集：若在 D 集中去除任何元素后 D 不再是支配集，則支配集 D 是極小支配集。最小支配集：G 的所有支配集中頂點個數(shù)最少的支配集。點基：設(shè) G(V，E)是一個有向圖，B 是若干個頂點組成的 V 的子集。如果對于任意的 VjV，都存在一個 ViB，使得 Vi 是 Vj 的

6、前代，則稱 B 是一個點基。最高強連通分支：設(shè)Si是有向圖 G 的一個強連通分支，如果在 G 中，不存在終點屬于Si而起點不熟于Si的弧，就稱Si為最高強連通分支。最小路徑覆蓋是指在有向無環(huán)圖 G 里面，覆蓋所有點的最少不相交簡單邊的集合，即每個點只屬于一條邊。最小路徑覆蓋數(shù)G 的定頂點數(shù)最小路徑覆蓋中的邊數(shù)。覆蓋集：K 是 G 圖的一個頂點子集且 G 的每一邊至少有一個端點屬于 K，則稱 K 是 G 的一個覆蓋。集：I 是 G 的一個頂點子集，I 中任兩個頂點不相鄰，則稱 I 是圖G 的一個集。極大集：若集 I 中增加任一個除 I 集外的頂點后 I 不是集。完全二分圖最佳匹配：權(quán)和最大的匹配

7、。完全匹配（完備匹配）：如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)。1.2集、覆蓋集、支配集之間關(guān)系(1) 一個(2) I 是集是極大集，當(dāng)且僅當(dāng)它是一個支配集；集，當(dāng)且僅當(dāng) G 中除 I 集外的所有頂點是一個覆蓋集；I 是極大(最大)集,當(dāng)且僅當(dāng) G 中除 I 集外的所有頂點是一個極小(最小)覆蓋集，即4ACM 常用模板(G)（覆蓋數(shù)）十(G)（覆蓋數(shù)）= G 的頂點數(shù)(3)極大集必為極小支配集，但是極小支配集未必是極大集。求所有極小支配集的公式：(V1，V2，Vm)(Vi 十U)一個頂點同與它相鄰的所有頂點進(jìn)行加法運算組成一個因子項，幾個因子項再連乘。連乘過程中展開成積之和形式。每

8、一積項給出一個極小支配集，所有積項給出了一切極小支配集。其中最小者為最小支配集。極小覆蓋集的計算方法：(V1，V2，Vm)(Vi 十U)某頂點的所有相鄰頂點進(jìn)行積運算后再與該頂點進(jìn)行和運算，組成一個因子項。幾個因子項連乘，并根據(jù)邏輯運算定律展開成積之和形式。每一積項給出一個極小覆蓋集，所有積項給出了一切極小覆蓋集，其中最小者為最小覆蓋集。極大集的計算方法：V-極小覆蓋集1.3DFS圖的 DFS 信息構(gòu)建g 矩陣: gij ->0: 無邊1: 可重復(fù)邊-1: 非可重復(fù)邊說明:以為在無向圖中 u->v之后就不能再從 v->u了故u, v了之后v,u要置-1。如果是有向圖gc 矩陣

9、:gcij->則沒有這個規(guī)則01234:無邊 樹枝邊反向邊正向邊交叉邊d 數(shù)組: f 數(shù)組: c 數(shù)組: p 數(shù)組: l 數(shù)組:b 數(shù)組:頂點的開始頂點的結(jié)束頂點顏色表時間表時間表0 白色 -1 灰色 1 黑色頂點的前驅(qū)表頂點的 L 值(最頂層的祖先層數(shù)) 頂點的度數(shù)表關(guān)于標(biāo)號函數(shù) LOW()LOW(U)代表的是與 U 以及 U 的子孫直接相連的結(jié)點的最高輩分（深度）dUU 首次被時LOWU =min(LOWU, dW)min(LOWU,const int maxn = 100;邊U,WLOWS)U 的兒子 S 的關(guān)聯(lián)邊全部被時5ACM 常用模板intint intn, gmaxnmax

10、n, gcmaxnmaxn;dmaxn, fmaxn, lmaxn, pmaxn, cmaxn, bmaxn; time;void dfs_visit(int u)/遞歸搜索以 U 為根的深度優(yōu)先樹int v;cu = -1;/置頂點為灰色/去掉這句之后適用于有向圖(后面設(shè)置不/可同)亦time+; du = time, lu for(v = 1; v<=n; v+)if(guv > 0)if(cv = 0)gvu = -1;=time;/如果 v 是白色節(jié)點/不可再/樹枝邊/度數(shù)gcuv =bu+;pv = u;1;/父親節(jié)點dist_visit(v); if(lv < l

11、u)lu = lv;gvu = 1;/遞歸搜索以v 為根的深度優(yōu)先樹/v 是 u 的后代/u 的兒子 v 的關(guān)聯(lián)邊搜索完后計算父親的/low 值/恢復(fù)可標(biāo)志elseif(cv < 0)if(lv </若頂點為灰色lu)/u 與 v 相連lugcuv=lv;2;/反向邊else/黑色if(dv > du) gcuv = 3;elsegcuv = 4;/正向邊/交叉邊 cu = 1;time+; fu = time;/DFS 完畢 置黑色吧void dfs()int u;6ACM 常用模板memset(gc, 0, sizeof(gc);memset(c, 0,memset(b,

12、 0,time = 0; for(u = 1; usizeof(c);sizeof(b);<= n; u+)if(cu = 0)pu = 0;dfs_visit(u);void DFS(int k, int father,int deep)int i, Ck =Dk =tot;-1; /灰色deep; /深度Ancestork = deep, tot for(i = 1; i<=n; +i)if(節(jié)點 i 和 k 相連)= 0;&& (i != father)&& (Ci = -1)Ancestork = Min(Ancestork, Di); if

13、(節(jié)點 i 與 k 相連) && (Ci = 0)DFS(i, k, deep + 1);tot+, Ancestork = Min(Ancestork, Ancestori);if(k = Root) && (tot > 1) | ( (k != Root) && (Ancestori >= Dk) ) Cutk = true;if(Ancestori > Dk)Brigeki = true;Ck = 1; /黑色time+, Ai = time;1.3.1割頂判定規(guī)則 1: 如果 root 節(jié)點有多于一個 1 子節(jié)點 則 r

14、oot 是割點判定規(guī)則 2: 如果一個節(jié)點 u 有某一個子節(jié)點 v 不含到 u 的祖先節(jié)點的后向邊，則 u 為割點即對于 u 的子節(jié)點 v, u 是割點的條：k = Root) && (tot > 1) | ( (k != Root) && (Ancestori >= Dk) )7ACM 常用模板1.3.2橋不屬于任何簡單回路的邊，條件：(Ancestori > Dk)1.3.3強連通分量強連通分量：(1) 對圖進(jìn)行 DFS，計下時間戳 Ai；(2) 改變 G 的每一條邊的方向，構(gòu)造出新圖 Gr；(3) 按 Ai 由大到小對 Gr 進(jìn)行 DFS

15、，構(gòu)建森林，每棵樹強連通分量。1.4最小點基(1) 找出圖 G(V，A)的所有強連通分支；(2) 從強連通分支中找出所有最高的強連通分支；(3) 從每一個最高的強連通分支中取一個權(quán)最小的頂點，組成的頂點集 B 就是一個G 的權(quán)最小的點基。1.5拓?fù)渑判騣nt int inttopol501, kk; /拓?fù)渑判虻慕Y(jié)果adjkj; /鄰接矩陣topo(int count,int vet)int i,j,k; int top=-1;for(i=1;i<=vet;i+) if(0=counti)counti=top; top=i;for(i=1;i<=vet;i+)if(-1=top)

16、return 0; k=top; top=counttop; topol+k = k; for(j=1;j<=vet;j+)if(adjkj)countj-;/有環(huán)8ACM 常用模板if(0=countj)countj=top; top=j;return 1;1.6歐拉路計算圖的歐拉路徑數(shù)目：設(shè) degreei表示結(jié)點 i 的入邊數(shù)目減去出邊數(shù)目，歐拉路徑數(shù)(|degreei|)/2+圖中沒有奇點的連通塊個數(shù)。算法步驟如下：(1) :任取一起始節(jié)點 VS;(2) :設(shè)路 EE：=v1,v2,v2,v3,.,vn,vs選出，則從 GEE 中選邊 ee，使 ee 與 VS相連，除非沒有其它選

17、擇，EE 不應(yīng)為 GEE 的橋（即去 GEE 應(yīng)保持連通性）; (3):重復(fù)步驟(2)，直至不能進(jìn)行下去為止。int graph5050;int degree50;vector<int> path;int n;/歐拉路void FindCircuit(int u)if(degreeu = 0)path.push_back(u); return;int v;for(v = 1; v <= n; +v) if(graphuv)-graphuv;-graphvu;-degreeu;-degreev; FindCircuit(v);path.push_back(u);9ACM 常用模

18、板1.7哈密頓路（正確？）(1) 從任意一個頂點開始，在它的任意一端鄰接一個頂點，構(gòu)造一條越來越長的鏈到不能在加長為止。設(shè)鏈為： r : y1 - y2 -L- ym(2) 檢查 y1 和 ym 是否鄰接：A） 如果 y1 和 ym 不鄰接，則轉(zhuǎn)到 3）；否則轉(zhuǎn)到 B）；B） 如果 mn，就說明這條鏈已經(jīng)把所有的點歷遍了，則停止構(gòu)造圈并輸出哈密頓圈r : y1 - y2 -L- ym 。否則 y1 和ym 不鄰接且 m<n，轉(zhuǎn)到 C）；C）找出一個不在 r 上的頂點 z 和在 r 上的頂點 yk，滿足 z 和 yk 是鄰接的，將 r 用下面長度為 m1 的鏈來代替： z - yk -L-

19、 ym - y1 -L- yk -1再轉(zhuǎn)到 2）；(3) 找到一個頂點 yk（1<k<m），滿足 y1 和 yk 鄰接，且 yk -1 和 ym 也是鄰接的，將 r 用下面的鏈來替代： y1 -L- yk -1 - ym -L- yk 。1.8Bellman-fordvoid relax(int u, int v)if(dv > du + euv)dv = du + euv;void bellman_ford()int i, j, k;for(i = 2; i <= n; i+)di = 10000000000;for(k = 1; k < n; k+) for(

20、i = 1; i <= n; i+)for(j = 1; j <= n; j+)relax(i, j);/*for(i = 1; i <= n; i+) for(j = 1; j <= n; j+)if(dj > di + eij) return false;return true;*/對每條邊松弛10ACM 常用模板1.9差分約束系統(tǒng)（用 bellman-ford 解）尋找滿足：Xj-Xibk(1i,jn,1km)的可行解 X。1.10 dag 最短路徑int int int intintn; graph501501;top501, k;/d501;flag50

21、1;拓?fù)渑判虻慕Y(jié)果(倒轉(zhuǎn)數(shù)組)void relax(int p, int q)if(dq < dp + graphpq)dq = dp+ graphpq;void dfs(int t)int i; flagt = 1;for(i = 1; i <= if(!flagidfs(i);n; i+)&& graphti)11ACM 常用模板top+k = t;void work()k =0;dfs(s);ds = 0;for(i = k; i > 0; i-) for(j = 1; j <= n; j+)if(graphtopij)relax(topi,j);

22、1.11 二分圖匹配一個關(guān)于二分圖的性質(zhì)：最大匹配數(shù)最大集XY1.11.1 匈牙利算法算廓：(1) 置 M 為空；(2) 找出一條增廣路徑 P，通過取反操作獲得更大的匹配 M代替 M；(3) 重復(fù)(2)操作直到找不出增廣路徑為止。int intintgraphmn;/二分圖的鄰接矩陣點是否被掃描過了匹配的方案，初始化為-1checkm;matchm;/intDfs(int p)int i,t;for(i = 1;i <=m; i+)if(graphip && !checki)checki=1; t=matchi; matchi=p;/檢查第二次if(t=-1 | Dfs(

23、t) return 1;matchi=t;return 0;intMatch()12ACM 常用模板int i, res=0;for(i = 1; i <= n;i+)memset(check,0,sizeof(check); if(Dfs(i)res+;return res;1.11.2 KM 算法KuhnMunkras 算法流程：(1) 初始化可行頂標(biāo)的值；(2) 用匈牙利算法尋找完備匹配；(3) 若未找到完備匹配則修改可行頂標(biāo)的值；(4) 重復(fù)(2)(3)直到找到相等子圖的完備匹配為止。Version 1：O(n4) const int size = 160;const int I

24、NF = 100000000;/ 相對無窮大bool mapsizesize;/ 二分圖的相等子圖, mapij = true 代表 Xi 與 Yj 有邊bool xckdsize, yckdsize;/ 標(biāo)記在一次 DFS 中，Xi 與Yi 是否在交錯樹上int matchsize; /保存匹配信息，其中 i 為Y 中的頂點標(biāo)號，matchi為 X 中頂點標(biāo)號/尋找是否有以 Xp 為起點的增廣路徑，返回值為是否含有增廣路bool DFS(int p, const int n)int i;for(i = 0; i < n; i+)if(!yckdiyckdi int t =&&a

25、mp; mappi)= true;matchi;matchi = if(t = -1matchi =p;| DFS(t, n)return true; t;if(t != -1) xckdt = true;return false;void KM_Perfect_Match(const int n, const int edgesize)13ACM 常用模板int i, j;int lxsize, lysize; for(i = 0; i < n; i+)/KM 算法中 Xi 與Yi 的標(biāo)號lxilyi for(j=-INF;0;0; j < n; j+) lxi = max(lx

26、i, edgeij);bool perfect = false; while(!perfect)/初始化鄰接矩陣for(i = 0; i < n; i+)for(j = 0; j < n; j+)if(lxi+lyj = edgeij) mapij else mapij = false;/ 匹配過程int live = 0;memset(match, -1, sizeof(match); for(i = 0; i < n; i+)memset(xckd, false, sizeof(xckd); memset(yckd, false, sizeof(yckd); if(DFS

27、(i, n) live+;elsexckdi = true; break;if(live = n) perfect = true; else/ 修改標(biāo)號過程int ex = INF;for(i = 0; i < n; i+)for(j = 0; xckdi && j < n; j+)=true;if(!yckdj) ex = min(ex, lxi+lyj-edgeij);14ACM 常用模板for(i = 0; i < n; i+)if(xckdi)if(yckdi)lxi -= ex;lyi += ex;int cost = 0;for(i = 0; i

28、< n; i+)cost += edgematchii;/ cost 為最大匹配的總和, match中保存匹配信息Version 2：O(n3)const int INF = 0x3fffffff;int int int intintn;w2020;/二分的權(quán)值lx20,ly20;fx20,fy20;/標(biāo)記在一次 DFS 中，Xi 與Yi 是否在交錯樹上matx20,maty20; /保存匹配信息intpath(int u)int v; fxu = 1;for (v=0; v<n; v+)if (lxu+lyv=wuv)&&(fyv<0) fyv = 1;if

29、 (matyv<0) | (path(matyv) matxu = v;matyv = u; return 1;return 0;intKM()int ret = 0,i,j,k,p; memset(ly,0,sizeof(ly); for (i=0; i<n; i+)15ACM 常用模板lxi = -INF;for (j=0; j<n; j+) if (wij > lxi)lxi = wij;memset(matx,-1,sizeof(matx); memset(maty,-1,sizeof(maty); for (i=0; i<n; i+) memset(fx

30、,-1,sizeof(fx);memset(fy,-1,sizeof(fy); if (!path(i)i-;p =forINF;(k=0; k<n; k+)if (fxk > 0)for (j=0; j<n; j+)if(fyj<0) && (lxk+lyj-wkj<p)p = j+)k+)lxk+lyj-wkj;lyj += (fyj<0 ? 0:p);lxk -= (fxk<0 ? 0:p);forfor(j=0; j<n;(k=0; k<n;for (i=0; i<n; i+) ret += wmatyii;

31、return ret;1.12 網(wǎng)絡(luò)流1.12.1 最大流尋求最大流的標(biāo)號法(增廣路算法：Ford,Fulkerson)從一個可行流(一般取零流)開始，不斷進(jìn)行以下的標(biāo)號過程與調(diào)整過程，直到找不到關(guān)于 f 的可增廣路徑為止。(1)標(biāo)號過程在這個過程中，網(wǎng)絡(luò)中的點分為已標(biāo)號點和未標(biāo)號點，已標(biāo)號點又分為已檢查和未檢查兩種。每個標(biāo)號點的標(biāo)號信息表示兩個 部分：第一標(biāo)號表明它的標(biāo)號從哪一點得到的，以便從 vt 開始反向追蹤找出也增廣路徑；第二標(biāo)號是為了表示該頂點是否已檢查過。標(biāo)號開始時，給 vs 標(biāo)上(s，0)，這時 vs 是標(biāo)號但末檢查的點，其余都是未標(biāo)號的點， 記為(0，0)。取一個標(biāo)號而未檢查的

32、點 vi，對于一切未標(biāo)號的點 vj：A對于弧(vi，vj)，若 fij<cij，則給 vj 標(biāo)號(vi，0)，這時，vj 點成為標(biāo)號而未檢查的點。B對于弧(vi，vj)，若 fji>0，則給 vj 標(biāo)號(-vi，0)，這時，vj 點成為標(biāo)號而未檢查的點。于是 vi 成為標(biāo)號且已檢查的點，將它的第二個標(biāo)號記為 1。重復(fù)上述步驟，一旦 vt 被標(biāo)上號，表明得到一條從 vi 到 vt 的增廣路徑 p，轉(zhuǎn)入調(diào)整過程。16ACM 常用模板若所有標(biāo)號都已檢查過去，而標(biāo)號過程進(jìn)行不下去時，則算法結(jié)束，這時的可行流就是最大流。(2)調(diào)整過程從 vt 點開始，通過每個點的第一個標(biāo)號，反向追蹤，可找出

33、增廣路徑 P。例如設(shè) vt 的第一標(biāo)號為 vk(或-vk)，則弧(vk，vt)(或 相應(yīng)地(vt，vk)是 p 上弧。接下來檢查 vk 的第一標(biāo)號，若為 vi(或-vi)，則找到(vi，vk)(或相應(yīng)地(vk，vi)。再檢查 vi 的第一 標(biāo)號，依此類推， 直到 vs 為止。這時整個增廣路徑就找到了。在上述找增廣路徑的同時計算 Q：Q=minmin(cij-fij)，minf*ij對流 f 進(jìn)行如下的修改：f'ij = f'ij =f'ij =fij+Q fij-Qf*ij(vi，vj) P 的前向弧的集合(vi，vj) P 的后向弧的集合(vi，vj)不屬于 P 的集

34、合接著，清除所有標(biāo)號，對新的可行流 f，重新進(jìn)入標(biāo)號過程。const int maxn = 1001; const int inf = 0x7fffffff;int int intintgmaxnmaxn;/網(wǎng)絡(luò)fmaxnmaxn;/殘留網(wǎng)絡(luò)vmaxn, premaxn; /用于標(biāo)號n, s, t;/節(jié)點數(shù),源,匯inline int min(int x, int y) return x<y?x:y;/更新殘留網(wǎng)絡(luò)void update()int p,q;int minval=vq=t; while (q!=s)p=preq;if (p>=n) p-=n, fqp-=minval;

35、 else fpq+=minval;q=p;intmax_flow()int queuemaxn, p, q, k, i; while (true)memset(pre, 0xff, sizeof(pre0)*n); pres = s;vs = inf;17ACM 常用模板queuep=q=0=s;/尋找增廣路while (p<=q)k=queuep+;for (i=0;i<n;i+) if (prei<0)if (gki > fki)vi=min(gki-fki, vk), prei=k, queue+q=i; if (fik > 0)vi=min(fik, v

36、k), prei=k+n, queue+q=i;if (pret>=0) break;if (pret<0) break; update();for (k=i=0;i<n;i+) k+=fsi; return k;1.12.2 上下界的網(wǎng)絡(luò)的最大流轉(zhuǎn)換成每條孤僅對應(yīng)一個容量 C(e)0 附加網(wǎng)絡(luò)：(1) 新增加兩個頂點 s和 t,s稱為附加源，t稱為附加匯；(2) 對原網(wǎng)絡(luò) N 的每個頂點 U，加一條新弧 eUt，這條弧的容量為所有以 U 為尾的弧的容量下限之和，即 C(e)B(e)；(3) 對原網(wǎng)絡(luò) N 的每個頂點 U，加一條新弧 esU，這條弧的容量為所有以 U 為頭的弧

37、的容量下限之和，即 C(e)B(e)；(4) 原網(wǎng)絡(luò) N 的每條弧在 C仍保留，弧容量 C(e)修正為 C(e)一 B(e)；(5) 再添兩條新弧 e=st, ets，e 的容量 C(e)inf，e的容量 C(e)inf。求附加網(wǎng) N的最大流，若結(jié)果能使流出 s的一切弧皆滿載(即s出發(fā)的所有弧 e，C(e)F(e)，則網(wǎng)絡(luò)有可行流 F(e)F(e)十 B(e)。否則原網(wǎng)無可行流。若 N網(wǎng)的最大流滿足上述條件，將可行流 F 放大，最終求出 N 網(wǎng)的最大流。1.12.3 上下界的網(wǎng)絡(luò)的最小流(1)(2)(3)(4)(5)按上述的辦法構(gòu)造附加網(wǎng) N;求 N網(wǎng)的最大流;流出附加源 s的弧都滿載？ 否，

38、N 網(wǎng)無最小流；求出 N 網(wǎng)和可行流 F(e)F(e)十 B(e)，倒向求解；以 t 為源點s 為匯點，最終求出的最大流即為從 s 到t 的最小流。18ACM 常用模板1.12.4 最小費用最大流構(gòu)造一個賦權(quán)有向圖 b(f)，它的頂點是原網(wǎng)絡(luò) N 中的頂點，而把 N 中每一條弧(vi，vj)變成兩個相反方向的弧(vi，vj)和(vj，vi)。定義 w(f)中的弧的權(quán)如下：如果(fij<cij)，則 bij=wij ；如果(fij=cij)，則 bij=+oo如果(fij>0)，則 bji=-wij ；如果(fij=cij)，則 bji=+oo于是在網(wǎng)絡(luò) N 中找關(guān)于f 的最小費用增

39、廣路徑就等價于在賦權(quán)有向圖 b(f)中，尋求從 vs 到vt 的最短路徑。求最短路有三種經(jīng)典算法，它們分別是 Dijkstra 算法、Floyd 算法和迭代算法(ford 算法）。由于在本問題中，賦權(quán)有向圖 b(f)中存在負(fù)權(quán)，故我們只能用后兩種方法求最短路，其中對于本問題最高效的算法是迭代算法。為了程序的實現(xiàn)方便，我們只要對原網(wǎng)絡(luò)做適當(dāng)?shù)恼{(diào)整。將原網(wǎng)絡(luò)中的每條弧(vi，vj)變成兩條相反的弧：前向弧(vi,vj)，其容量 cij 和費用 wij 不變，流量為 fij； 后向弧(vj,vi)，其容量 0 和費用-wij，流量為-fij。事實上，對于原網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)中，這些單元已存在，在用標(biāo)號法

40、求最大流時是閑置的。這樣我們就不必產(chǎn)生關(guān)于流 f 的有向圖 b(f)。同時對(vi,vj)的流量可否改時，可以統(tǒng)一為是否“fij<cij”。因為對于后向弧(vj，vi)，若 fij>0，則 fji=-fij<0=cji。#define Q (adjwv.cap<0? -adjwv.flow : adjwv.cap-adjwv.flow) #define maxV 100/dfs 增廣路徑-最大流#define maxWT 99999struct link int flow;int cap;adjmaxVmaxV;int stmaxV;int vtmaxV;int V;i

41、nt ft;int flowdfs(int w,int t) int v,d;vtw=1;if(w=t)ft=1;return maxWT;for(v=0;v<V;v+)if(Q>0 && vtv=0)d=flowdfs(v,t); stv=w;if(ft=1) return (Q>d?d:Q);return 0; int main()int n,a,b,c,i,j,d; int s,t,x,flow=0;scanf("%d%d",&V,&n); for(i=0;i<V;i+)for(j=0;j<V;j+)adj

42、ij.flow=adjij.cap=0; for(i=1;i<=n;i+) scanf("%d%d%d",&a,&b,&c);19ACM 常用模板adjab.cap=c;adjba.cap=-c;scanf("%d%d",&s,&t); memset(vt,0,sizeof(vt); ft=0; while(d=flowdfs(s,t)!=0) flow+=d; for(x=t;x!=s;x=stx)adjstxx.flow += d;adjxstx.flow -= d;memset(vt,0,sizeof(

43、vt);ft=0;printf("maxflow = %dn",flow); return 0;* #define Q (adjwv.cap<0?-adjwv.flow:adjwv.cap-adjwv.flow)#define maxV 105/最小費用最大流#define maxWT 99999 struct linkint flow, cost, cap;adjmaxVmaxV; int V;int wtmaxV; /int stmaxV; /最短距離最短路int maxflow(int s,int t)bool ft; int w, v, d;for(v=0;v

44、<V;v+) wtv=maxWT; wts=0;doft=1;for(w=0;w<V-1;w+) if(wtw<maxWT)for(v=1;v<V;v+)if(Q > 0&& adjwv.cap!=0)if(wtw + adjwv.cost < wtv)20ACM 常用模板wtv=wtw+adjwv.cost; stv=w;ft=0;while(!ft); if(wtt<maxWT)for(v=t,d=maxWT;v!=s;v=stv)w=stv;d=(Q > d ? d : Q);return d;elsereturn 0;in

45、t netcost()int total=0,i,j; for(i=0;i<V;i+)for(j=0;j<V;j+)if(adjij.cap>0) return total;total+=adjij.flow*adjij.cost;int main()int n,a,b,Cap,Cost,i,j,d; int s,t,x,flow=0,cost; scanf("%d%d",&V,&n); for(i=0;i<V;i+)for(j=0;j<V;j+)adjij.flow=adjij.cap=adjij.cost=0; for(i=

46、1;i<=n;i+)scanf("%d%d%d%d",&a,&b,&Cap,&Cost); adjab.cap=Cap;adjba.cap=-Cap; adjab.cost=Cost; adjba.cost=-Cost;scanf("%d%d",&s,&t);21ACM 常用模板while(d=maxflow(s,t)!=0)flow+=d; for(x=t;x!=s;x=stx)adjstxx.flow += d;adjxstx.flow -= d;printf("maxflow = %d

47、n",flow); cost=netcost();printf("mincost = %dn",cost);return 0;1.12.5 上下界的網(wǎng)絡(luò)的最小費用最小流(1) 同上下界的網(wǎng)絡(luò)的最小流;(2) 為了尋求關(guān)于 F 的最小費用，我們構(gòu)造一個賦權(quán)有向圖 W(F)，它的頂點是原 N 網(wǎng)的頂點，而把 N 中的每一條弧(Vi，Vj)變成兩條相反方向的弧(Vi，Vj)和(Vj，Vi)，定義 W(F) 中的弧的權(quán)為：Wij = -Aij(Fij>Bij),Wij = 0(Fij<=Bij && j = i)在 W(F)中尋求一條從 Vs

48、到 Vt 的最短路;(3) 若存在最短路，則在原 N 網(wǎng)中得到相應(yīng)的可改進(jìn)路 P，這條可改進(jìn)路的前向弧 P 十為最短路上 F 值大于 B 值的弧的集合，后向弧 P 一為最短路上 F 值小于或等于 B 值的弧的集合。在可改進(jìn)路 P 上對F 進(jìn)行調(diào)整，調(diào)整量為：Qminmin(P+)(F(e)一 B(e)，min(p-)(c(e)-F(e)從 t 頂點出發(fā)，向 s 頂點倒推，按下述規(guī)律縮小可行流:F(e) = F(e)+Q(P-) F(e) = F(e)-Q(P+)2數(shù)論2.1最大公約數(shù)int(int a,int b)If(b>a)return(b, a);if(b=0) return a;

49、else return(b,a%b);22ACM 常用模板2.2最小公倍數(shù) lcmlcm(a, b) = a*b/(a, b)2.3快速冪取模 BLmodP(O(logb)int power(int B, int L, int P)int acc = 1, q;for(q = L; q; q >>= 1)if(q & 1) acc = (_int64)acc * B % P; B = (_int64)B * B % P;return acc;2.4Fermat 小定理如果 p 是一個素數(shù)，則對任意 a 有 a p º a (mod p)。特別的，如果 p 不能整除 a，則還有a p-1 º 1 (mod p)。2.5Rabin-Miller 偽素數(shù)測試int Rabin-Miller(int n)int i;for(i = 1; i <= s; +i)int a = rand()%(n-2)+2; if(power(a, n-1, n) != 1) return 0;return 1;2.6Pollard-rho在開始時選取 0n-1 范圍內(nèi)的隨機