浅谈基于分层思想的网络流算法.htm

浅谈基于分层思想的网络流算法 介绍分层思想的网络流算法

<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><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-element:field-begin'></span></span><span
style='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'><span
style='mso-element:field-separator'></span></span><![endif]--><span
style='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'><span
style='mso-element:field-end'></span></span><![endif]--></a></span></span><span
lang=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><a
href="#_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<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><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-element:field-begin'></span></span><span
style='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'><span
style='mso-element:field-separator'></span></span><![endif]--><span
style='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'><span
style='mso-element:field-end'></span></span><![endif]--></a></span></span><span
lang=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'><span
class=MsoHyperlink><span lang=EN-US style='mso-no-proof:yes'><a
href="#_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><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-element:field-begin'></span></span><span
style='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'><span
style='mso-element:field-separator'></span></span><![endif]--><span
style='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'><span
style='mso-element:field-end'></span></span><![endif]--></a></span></span><span
lang=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'><span
class=MsoHyperlink><span lang=EN-US style='mso-no-proof:yes'><a
href="#_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>复杂度分析</span></span><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-element:field-begin'></span></span><span
style='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'><span
style='mso-element:field-separator'></span></span><![endif]--><span
style='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'><span
style='mso-element:field-end'></span></span><![endif]--></a></span></span><span
lang=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><a
href="#_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>七、总结</span></span><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-tab-count:1 dotted'>... </span></span><!--[if supportFields]><span
style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;
text-underline:none'><span style='mso-element:field-begin'></span></span><span
style='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'><span
style='mso-element:field-separator'></span></span><![endif]--><span
style='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'><span
style='mso-element:field-end'></span></span><![endif]--></a></span></span><span
lang=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]><b
style='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'><span
lang=EN-US style='font-size:16.0pt;line-height:125%;font-family:黑体'>[</span></b><b
style='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]><span
lang=EN-US style='mso-bidi-font-family:宋体'><span style='mso-list:Ignore'>一、<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</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>&nbsp;</o:p></span></p>

<p class=MsoNormal style='text-indent:24.0pt;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"'>图论这门古老而又年轻的学科</span><a
style='mso-footnote-id:ftn1' href="#_ftn1" name="_ftnref1" title=""><span
class=MsoFootnoteReference><span lang=EN-US style='font-size:12.0pt;line-height:
150%'><span style='mso-special-character:footnote'><![if !supportFootnotes]><span
class=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><span
style='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><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"'>在信息学竞赛中占据了相当大的比重。其中，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。</span><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;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"'>随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的</span><span
lang=EN-US style='font-size:12.0pt;line-height:150%'>3</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"'>个网络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。</span><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>&nbsp;</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>&nbsp;</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"'>二、预备概念</span></a><a
style='mso-footnote-id:ftn2' href="#_ftn2" name="_ftnref2" title=""><span
style='mso-bookmark:_Toc157495090'><span class=MsoFootnoteReference><span
lang=EN-US><span style='mso-special-character:footnote'><![if !supportFootnotes]><span
class=MsoFootnoteReference><b style='mso-bidi-font-weight:normal'><span
lang=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><span
lang=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><span
style='mso-bookmark:_Toc157495090'></span></h1>

<h2><a name="_Toc157495091"><span lang=EN-US>2.1</span></a><span
style='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"'>给定一个流量网络</span><span
lang=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=23
src="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"'>、源点</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=15
src="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"'>、汇点</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=16
src="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"'>、容量函数</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=15
src="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"'>，以及其上的流量函数</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