📄 浅谈基于分层思想的网络流算法.htm
字号:
mso-list-template-ids:-748107054 828423888 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}@list l2:level1 {mso-level-text:（%1）; mso-level-tab-stop:57.75pt; mso-level-number-position:left; margin-left:57.75pt; text-indent:-36.0pt;}@list l3 {mso-list-id:1210923445; mso-list-type:hybrid; mso-list-template-ids:-880761438 1517832120 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}@list l3:level1 {mso-level-text:%1、; mso-level-tab-stop:36.0pt; mso-level-number-position:left; text-indent:-36.0pt;}ol {margin-bottom:0cm;}ul {margin-bottom:0cm;}--></style><!--[if gte mso 10]><style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}table.MsoTableGrid {mso-style-name:网格型; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; border:solid windowtext 1.0pt; mso-border-alt:solid windowtext .5pt; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-border-insideh:.5pt solid windowtext; mso-border-insidev:.5pt solid windowtext; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}</style><![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="2050"/></xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--></head><body lang=ZH-CN link=blue vlink=purple style='tab-interval:21.0pt;text-justify-trim:punctuation'><div class=Section1 style='layout-grid:15.6pt'><p class=MsoNormal align=center style='text-align:center;line-height:150%'><spanlang=EN-US style='font-size:24.0pt;line-height:150%;font-family:华文行楷'><o:p> </o:p></span></p><p class=MsoNormal align=center style='text-align:center;line-height:150%'><spanlang=EN-US style='font-size:24.0pt;line-height:150%;font-family:华文行楷'><o:p> </o:p></span></p><p class=MsoNormal align=center style='text-align:center;line-height:150%'><spanstyle='font-size:24.0pt;line-height:150%;font-family:华文行楷'>浅谈基于分层思想的网络流算法<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:266.0pt;mso-char-indent-count:19.0;line-height:150%'><span style='font-size:14.0pt;line-height:150%;font-family:楷体_GB2312'>上海市延安中学 王欣上<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='line-height:150%'><span lang=EN-US style='font-size:14.0pt;line-height:150%;font-family:楷体_GB2312'><o:p> </o:p></span></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'>[</span></b><b style='mso-bidi-font-weight:normal'><span style='font-size:16.0pt;line-height:150%;font-family:黑体'>关键字<span lang=EN-US>]</span></span></b><spanlang=EN-US style='font-size:14.0pt;line-height:150%;font-family:楷体_GB2312'><o:p></o:p></span></p><p class=MsoNormal style='text-indent:21.0pt;line-height:150%'><spanstyle='font-size:16.0pt;line-height:150%;font-family:黑体'>层次图<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span></span>网络流<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span></span>基本算法<span lang=EN-US><spanstyle='mso-spacerun:yes'> </span></span>应用<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:21.0pt;line-height:150%'><spanlang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'>MPLA<spanstyle='mso-spacerun:yes'> </span>Dinic<spanstyle='mso-spacerun:yes'> </span>MPM<o:p></o:p></span></p><p class=MsoNormal style='text-indent:21.0pt;line-height:150%'><spanlang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:12.0pt;line-height:150%'><o:p> </o:p></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:12.0pt;line-height:150%'><o:p> </o:p></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:12.0pt;line-height:150%'><o:p> </o:p></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'>[</span></b><b style='mso-bidi-font-weight:normal'><span style='font-size:16.0pt;line-height:150%;font-family:黑体'>摘要<span lang=EN-US>]<o:p></o:p></span></span></b></p><p class=MsoNormal style='text-indent:21.75pt;line-height:150%'><spanstyle='font-size:16.0pt;line-height:150%;font-family:黑体'>本文详细地介绍了基于层次图概念的三种算法，并通过例题来说明<spanlang=EN-US>Dinic</span>算法在信息学竞赛中的优越性。<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal style='text-indent:21.75pt;line-height:150%'><bstyle='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoNormal style='text-indent:21.75pt;line-height:150%'><bstyle='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoNormal style='text-indent:21.75pt;line-height:150%'><bstyle='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoNormal style='text-indent:21.75pt;line-height:150%'><bstyle='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'>[</span></b><b style='mso-bidi-font-weight:normal'><span style='font-size:16.0pt;line-height:150%;font-family:黑体'>目录<span lang=EN-US>]<o:p></o:p></span></span></b></p><p class=MsoNormal style='line-height:150%'><b style='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:16.0pt;line-height:150%;font-family:黑体'><o:p> </o:p></span></b></p><p class=MsoToc1 style='tab-stops:42.0pt right dotted 414.8pt'><!--[if supportFields]><bstyle='mso-bidi-font-weight:normal'><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:14.0pt;line-height:125%;font-family:宋体'><spanstyle='mso-element:field-begin'></span><spanstyle='mso-spacerun:yes'> </span>TOC \o "1-2" \h \z \u <spanstyle='mso-element:field-separator'></span></span></b><![endif]--><spanclass=MsoHyperlink><span lang=EN-US><a href="#_Toc157495089"><span lang=EN-USstyle='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'><spanstyle='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 _Toc157495089 \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'>3</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000380039000000</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=MsoToc1><span class=MsoHyperlink><span lang=EN-US><ahref="#_Toc157495090"><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 _Toc157495090 \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'>3</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390030000000</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="#_Toc157495091">2.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 _Toc157495091 \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'>3</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390031000000</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="#_Toc157495092">2.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><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 _Toc157495092 \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'>4</span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none;text-underline:none'><!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100350037003400390035003000390032000000</w:data>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -