3、小了。于是可以縮小二分的范圍，直至找到恰好等于0的解。[注意精度]分?jǐn)?shù)規(guī)劃最優(yōu)比率生成樹每邊有兩權(quán)值(a,b)，求∑a/∑b最小的生成樹邊權(quán)變?yōu)閍-k*b后求MST，看是否<0最小平均環(huán)路每邊有兩權(quán)值(a,b)，在圖中找一個(gè)環(huán)，使得環(huán)上所有的∑a/∑b最小邊權(quán)變成a-k*b后，Bellman-ford(SPFA)找負(fù)環(huán)最大密度子圖回到原題，密度定義
4、E
5、/
6、V
7、=k假設(shè)答案為k，則要求解的問題是：選出一個(gè)合適的點(diǎn)集V和邊集E，令(
8、E
9、-k*
10、V
11、)取得最大值所謂“合適”是指滿足如下限制：若選擇某條邊，則必選擇其兩端點(diǎn)最大密度子圖以原圖的邊作為左側(cè)頂點(diǎn)，則原圖的點(diǎn)作為右側(cè)頂點(diǎn)。左側(cè)點(diǎn)有正權(quán)值+
12、1，右側(cè)點(diǎn)有負(fù)權(quán)值-k若原圖中存在邊(u,v)，則新圖中添加兩條邊([uv]?u),([uv]?v)最大權(quán)閉合子圖!最大密度子圖新圖中點(diǎn)數(shù)為m+n，不太理想。能否只用原圖中的點(diǎn)建立網(wǎng)絡(luò)？最大密度子圖如上圖，要統(tǒng)計(jì)的邊為點(diǎn)集關(guān)聯(lián)的所有邊除去紅色的邊可發(fā)現(xiàn)紅色的邊恰為一個(gè)割Max{
13、E
14、-k*
15、V
16、}?-Min{k*
17、V
18、-
19、E
20、}
21、E
22、=(
23、V
24、中點(diǎn)度數(shù)之和–(
25、V
26、與
27、V
28、的補(bǔ)之割))/2最大密度子圖
29、E
30、=V中點(diǎn)度數(shù)之和–(V與V的補(bǔ)之割))/2=(∑v∈Vdv–c[V,V’])/2為便于計(jì)算，擴(kuò)大2倍，化簡得最大密度子圖選出一個(gè)點(diǎn)集V，里面每選一個(gè)點(diǎn)v的花費(fèi)是2k-dv，這部分花費(fèi)再加上V
31、和它的補(bǔ)集之前的割，要求總和最小能否把這個(gè)總和計(jì)入一個(gè)割里？最大密度子圖把原圖的無向邊變成雙向的有向邊（注：此處沒有必要拆點(diǎn)），容量為1。添加S,T。添加從S到每個(gè)點(diǎn)的邊，容量為0(why?)。對每個(gè)點(diǎn)添加指向T的邊，容量為2k-dv,求此網(wǎng)絡(luò)的最小割。注意：邊權(quán)為負(fù)怎么辦？最大密度子圖對于此題，處理方法很簡單，對每條從S發(fā)出和指向T的邊，都增加一個(gè)足夠大的值U，使得所有邊權(quán)非負(fù)。此時(shí)總的最大流值增加U*n。設(shè)上述最大流（最小割）為C，則判斷C-U*n的正負(fù)情況，即可決定開始猜測的k是偏大還是偏小。最大密度子圖凸費(fèi)用流問題凸函數(shù)：函數(shù)的曲線始終在其切線上方f(y)>=f(x)+f’(x)(y-
32、x)例如y=x^2(x>0)凸費(fèi)用流問題是指，費(fèi)用與流量成凸函數(shù)關(guān)系（而不是經(jīng)典的線性關(guān)系）凸費(fèi)用流問題因?yàn)榱髁砍Ｏ薅檎麛?shù)，故費(fèi)用函數(shù)可看作“分段”為凸。類似下圖所示：凸費(fèi)用流問題一個(gè)實(shí)用解法：拆邊根據(jù)費(fèi)用函數(shù)的“折點(diǎn)”把邊拆成費(fèi)用不同的若干條邊。例如：某邊容量上限為3，費(fèi)用為f(x)=x^2則可把該邊拆成3條邊，容量均為1，費(fèi)用依次為1^2-0^2=1,2^2–1^2=3,3^2–2^2=5凸費(fèi)用流問題由費(fèi)用流的“貪心”性質(zhì)可知，若某兩點(diǎn)之間有多條邊，必然會(huì)先填滿費(fèi)用較小的邊。故當(dāng)此邊流過1個(gè)流量時(shí)，費(fèi)用為1，流量為2時(shí)，費(fèi)用為1+3=4，依次類推思考：為什么要限定“凸”？平面圖最大流與普
33、通流網(wǎng)絡(luò)的唯一不同：圖是由平面圖構(gòu)建而來即平面圖中的一塊區(qū)域作為一個(gè)點(diǎn)，相鄰區(qū)域之間連邊所得到的圖有何特殊性質(zhì)？平面圖最大流ACMBeijing2019如下圖所示，邊上有權(quán)值，要阻斷從左上角到右下角的 的全部路，最 小花費(fèi)多少1000*1000矩陣平面圖最大流ST平面圖最大流把每個(gè)面當(dāng)作一個(gè)點(diǎn)，原問題轉(zhuǎn)變?yōu)榍骃到T的最短路問題無向圖最小割與普通最小割不同之處：不限定源與匯，隨便割成兩部分即可枚舉？
