?? 淺談基于分層思想的網(wǎng)絡(luò)流算法.htm
字號(hào):
<span lang=EN-US style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'><span lang=EN-US>矩陣游戲</span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-begin'></span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'> PAGEREF _Toc157495104 \h </span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-separator'></span></span><![endif]--><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'>18</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300034000000</w:data></xml><![endif]--></span><!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-end'></span></span><![endif]--></a></span></span><spanlang=EN-US style='font-size:10.5pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'><o:p></o:p></span></p><p class=MsoToc1><span class=MsoHyperlink><span lang=EN-US><ahref="#_Toc157495105"><span lang=EN-US style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'><span lang=EN-US>六、</span></span>MPM<spanlang=EN-US style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'><span lang=EN-US>的算法步驟以及復(fù)雜度分析</span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-begin'></span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'> PAGEREF _Toc157495105 \h </span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-separator'></span></span><![endif]--><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'>19</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300035000000</w:data></xml><![endif]--></span><!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-end'></span></span><![endif]--></a></span></span><spanlang=EN-US style='font-size:10.5pt;mso-bidi-font-size:12.0pt;line-height:125%'><o:p></o:p></span></p><p class=MsoToc2 style='tab-stops:right dotted 414.8pt'><spanclass=MsoHyperlink><span lang=EN-US style='mso-no-proof:yes'><ahref="#_Toc157495106">6.1<span lang=EN-US style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'><span lang=EN-US>算法步驟</span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-begin'></span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'> PAGEREF _Toc157495106 \h </span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-separator'></span></span><![endif]--><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'>19</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300036000000</w:data></xml><![endif]--></span><!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-end'></span></span><![endif]--></a></span></span><spanlang=EN-US style='font-size:10.5pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'><o:p></o:p></span></p><p class=MsoToc2 style='tab-stops:right dotted 414.8pt'><spanclass=MsoHyperlink><span lang=EN-US style='mso-no-proof:yes'><ahref="#_Toc157495107">6.2<span lang=EN-US style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'><span lang=EN-US>復(fù)雜度分析</span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-begin'></span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'> PAGEREF _Toc157495107 \h </span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-separator'></span></span><![endif]--><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'>20</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300037000000</w:data></xml><![endif]--></span><!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-end'></span></span><![endif]--></a></span></span><spanlang=EN-US style='font-size:10.5pt;mso-bidi-font-size:12.0pt;mso-no-proof:yes'><o:p></o:p></span></p><p class=MsoToc1><span class=MsoHyperlink><span lang=EN-US><ahref="#_Toc157495108"><span lang=EN-US style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'><span lang=EN-US>七、總結(jié)</span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-begin'></span></span><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'> PAGEREF _Toc157495108 \h </span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-separator'></span></span><![endif]--><spanstyle='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'>21</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300038000000</w:data></xml><![endif]--></span><!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><spanstyle='mso-element:field-end'></span></span><![endif]--></a></span></span><spanlang=EN-US style='font-size:10.5pt;mso-bidi-font-size:12.0pt;line-height:125%'><o:p></o:p></span></p><p class=MsoNormal style='line-height:125%'><!--[if supportFields]><bstyle='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:12.0pt;line-height:125%;font-family:宋體;mso-no-proof:yes'><span style='mso-element:field-end'></span></span></b><![endif]--><b style='mso-bidi-font-weight:normal'><spanlang=EN-US style='font-size:16.0pt;line-height:125%;font-family:黑體'>[</span></b><bstyle='mso-bidi-font-weight:normal'><span style='font-size:16.0pt;line-height:125%;font-family:黑體'>正文<span lang=EN-US>]<o:p></o:p></span></span></b></p><h1 style='margin-left:44.25pt;text-indent:-44.25pt;mso-list:l1 level1 lfo3;tab-stops:list 44.25pt'><a name="_Toc157495089"><![if !supportLists]><spanlang=EN-US style='mso-bidi-font-family:宋體'><span style='mso-list:Ignore'>一、<spanstyle='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>引言</span></a></h1><p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='text-indent:24.0pt;line-height:150%'><spanstyle='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>圖論這門古老而又年輕的學(xué)科</span><astyle='mso-footnote-id:ftn1' href="#_ftn1" name="_ftnref1" title=""><spanclass=MsoFootnoteReference><span lang=EN-US style='font-size:12.0pt;line-height:150%'><span style='mso-special-character:footnote'><![if !supportFootnotes]><spanclass=MsoFootnoteReference><span lang=EN-US style='font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:宋體;mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'>[</span><spanstyle='font-size:12.0pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'>①</span><span lang=EN-US style='font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:宋體;mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'>]</span></span><![endif]></span></span></span></a><spanstyle='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>在信息學(xué)競賽中占據(jù)了相當(dāng)大的比重。其中，網(wǎng)絡(luò)流算法經(jīng)常在題目中出現(xiàn)。網(wǎng)絡(luò)流涵蓋的知識(shí)非常豐富，從基本的最小割最大流定理到網(wǎng)絡(luò)的許多變形再到最高標(biāo)號(hào)預(yù)流推進(jìn)的六個(gè)優(yōu)化等等，同學(xué)們?cè)谄綍r(shí)需要多多涉獵這方面的知識(shí)，不斷積累，才能應(yīng)對(duì)題目的各種變化。</span><spanlang=EN-US style='font-size:12.0pt;line-height:150%'><o:p></o:p></span></p><p class=MsoNormal style='text-indent:24.0pt;line-height:150%'><spanstyle='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>隨著信息學(xué)競賽的不斷發(fā)展，其題目的難度以及考察范圍都不斷增大。現(xiàn)在，對(duì)于一些新出現(xiàn)的題目，僅僅掌握最樸素的網(wǎng)絡(luò)流算法并不足以解決問題。本文針對(duì)一些數(shù)據(jù)規(guī)模比較大的網(wǎng)絡(luò)流題目詳細(xì)介紹了基于分層思想的</span><spanlang=EN-US style='font-size:12.0pt;line-height:150%'>3</span><spanstyle='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>個(gè)網(wǎng)絡(luò)流算法，并通過列舉和比較說明了其在解題中的應(yīng)用，而對(duì)一些基礎(chǔ)的知識(shí)，如最小割最大流定理等，沒有作具體闡釋，大家可以在許多其他網(wǎng)絡(luò)流資料中找到。</span><spanlang=EN-US style='font-size:12.0pt;line-height:150%'><o:p></o:p></span></p><p class=MsoNormal style='text-indent:24.0pt;mso-char-indent-count:2.0;line-height:150%'><span lang=EN-US style='font-size:12.0pt;line-height:150%'><o:p> </o:p></span></p><p class=MsoNormal style='text-indent:24.0pt;mso-char-indent-count:2.0;line-height:150%'><span lang=EN-US style='font-size:12.0pt;line-height:150%'><o:p> </o:p></span></p><h1><a name="_Toc157495090"><span style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>二、預(yù)備概念</span></a><astyle='mso-footnote-id:ftn2' href="#_ftn2" name="_ftnref2" title=""><spanstyle='mso-bookmark:_Toc157495090'><span class=MsoFootnoteReference><spanlang=EN-US><span style='mso-special-character:footnote'><![if !supportFootnotes]><spanclass=MsoFootnoteReference><b style='mso-bidi-font-weight:normal'><spanlang=EN-US style='font-size:22.0pt;font-family:"Times New Roman";mso-fareast-font-family:宋體;mso-font-kerning:22.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'>[</span><span style='font-size:22.0pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";mso-font-kerning:22.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'>②</span><spanlang=EN-US style='font-size:22.0pt;font-family:"Times New Roman";mso-fareast-font-family:宋體;mso-font-kerning:22.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA'>]</span></b></span><![endif]></span></span></span></span></a><spanstyle='mso-bookmark:_Toc157495090'></span></h1><h2><a name="_Toc157495091"><span lang=EN-US>2.1</span></a><spanstyle='mso-bookmark:_Toc157495091'><span style='font-family:黑體;mso-ascii-font-family:Arial'>剩余圖的概念</span></span></h2><p class=MsoNormal style='text-indent:24.0pt;mso-char-indent-count:2.0;line-height:150%'><span style='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>給定一個(gè)流量網(wǎng)絡(luò)</span><spanlang=EN-US style='font-size:12.0pt;line-height:150%'><sub><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter"/> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"/> <v:f eqn="sum @0 1 0"/> <v:f eqn="sum 0 0 @1"/> <v:f eqn="prod @2 1 2"/> <v:f eqn="prod @3 21600 pixelWidth"/> <v:f eqn="prod @3 21600 pixelHeight"/> <v:f eqn="sum @0 0 1"/> <v:f eqn="prod @6 1 2"/> <v:f eqn="prod @7 21600 pixelWidth"/> <v:f eqn="sum @8 21600 0"/> <v:f eqn="prod @7 21600 pixelHeight"/> <v:f eqn="sum @10 21600 0"/> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/> <o:lock v:ext="edit" aspectratio="t"/></v:shapetype><v:shape id="_x0000_i1030" type="#_x0000_t75" style='width:63.75pt; height:17.25pt' o:ole=""> <v:imagedata src="fencen.files/image001.wmz" o:title=""/></v:shape><![endif]--><![if !vml]><img width=85 height=23src="fencen.files/image002.gif" v:shapes="_x0000_i1030"><![endif]></sub><!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1030" DrawAspect="Content" ObjectID="_1254728668"> </o:OLEObject></xml><![endif]--></span><span style='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、源點(diǎn)</span><span lang=EN-US style='font-size:12.0pt;line-height:150%'><sub><!--[if gte vml 1]><v:shape id="_x0000_i1031" type="#_x0000_t75" style='width:9pt;height:11.25pt' o:ole=""> <v:imagedata src="fencen.files/image003.wmz" o:title=""/></v:shape><![endif]--><![if !vml]><img width=12 height=15src="fencen.files/image004.gif" v:shapes="_x0000_i1031"><![endif]></sub><!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1031" DrawAspect="Content" ObjectID="_1254728669"> </o:OLEObject></xml><![endif]--></span><span style='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、匯點(diǎn)</span><span lang=EN-US style='font-size:12.0pt;line-height:150%'><sub><!--[if gte vml 1]><v:shape id="_x0000_i1032" type="#_x0000_t75" style='width:6.75pt;height:12pt' o:ole=""> <v:imagedata src="fencen.files/image005.wmz" o:title=""/></v:shape><![endif]--><![if !vml]><img width=9 height=16src="fencen.files/image006.gif" v:shapes="_x0000_i1032"><![endif]></sub><!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1032" DrawAspect="Content" ObjectID="_1254728670"> </o:OLEObject></xml><![endif]--></span><span style='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>、容量函數(shù)</span><span lang=EN-US style='font-size:12.0pt;line-height:150%'><sub><!--[if gte vml 1]><v:shape id="_x0000_i1033" type="#_x0000_t75" style='width:9pt;height:11.25pt' o:ole=""> <v:imagedata src="fencen.files/image007.wmz" o:title=""/></v:shape><![endif]--><![if !vml]><img width=12 height=15src="fencen.files/image008.gif" v:shapes="_x0000_i1033"><![endif]></sub><!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1033" DrawAspect="Content" ObjectID="_1254728671"> </o:OLEObject></xml><![endif]--></span><span style='font-size:12.0pt;line-height:150%;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，以及其上的流量函數(shù)</span><span lang=EN-US style='font-size:12.0pt;line-height:150%'><sub><!--[if gte vml 1]><v:shape id="_x0000_i1034" type="#_x0000_t75" style='width:1?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -