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

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

</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="#_Toc157495093">2.3<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 _Toc157495093 \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'>4</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390033000000</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="#_Toc157495094">2.4<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 _Toc157495094 \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'>5</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390034000000</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="#_Toc157495095"><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>(MPLA)<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 _Toc157495095 \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'>5</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390035000000</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="#_Toc157495096">3.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 _Toc157495096 \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'>5</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390036000000</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="#_Toc157495097">3.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 _Toc157495097 \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'>6</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390037000000</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="#_Toc157495098">3.3<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 _Toc157495098 \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'>8</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390038000000</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="#_Toc157495099"><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>Dinic<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 _Toc157495099 \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'>9</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390039000000</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="#_Toc157495100">4.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 _Toc157495100 \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'>9</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300030000000</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="#_Toc157495101">4.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 _Toc157495101 \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'>13</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300031000000</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="#_Toc157495102"><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>Dinic<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 _Toc157495102 \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'>15</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300032000000</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="#_Toc157495103"><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>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>(profit)<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 _Toc157495103 \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'>15</span><span style='color:windowtext;display:none;
mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml>
 <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003100300033000000</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="#_Toc157495104"><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>2