{"id":6358,"date":"2024-08-11T09:01:03","date_gmt":"2024-08-11T01:01:03","guid":{"rendered":""},"modified":"2024-08-11T09:01:03","modified_gmt":"2024-08-11T01:01:03","slug":"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5","status":"publish","type":"post","link":"https:\/\/mushiming.com\/6358.html","title":{"rendered":"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5"},"content":{"rendered":"<p><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"display: none;\"> \n <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path> \n<\/svg> <\/p>\n<div class=\"toc\">\n<div class=\"toc\">\n<ul>\n<li>\u95ee\u9898\u5b9a\u4e49<\/li>\n<li>\u9650\u5236\u6761\u4ef6<\/li>\n<li>\u793a\u4f8b<\/li>\n<li>\u57fa\u672c\u601d\u60f3<\/li>\n<li>\u5f15\u5165\u53cd\u5411\u8fb9<\/li>\n<li>Edmond-Karp\u7b97\u6cd5<\/li>\n<li>Ford-Fulkerson\u7b97\u6cd5<\/li>\n<li>\u4f7f\u7528DFS\u7684Ford-Fulkerson\u7b97\u6cd5\n<ul>\n<li>\u9012\u5f52\u8bbe\u8ba1\u9519\u8bef\u793a\u8303<\/li>\n<li>\u9012\u5f52\u6b63\u786e\u8bbe\u8ba1<\/li>\n<li>\u9012\u5f52\u6b21\u6570\u4f18\u5316<\/li>\n<li>\u6700\u5927\u6d41\u56fe\u7684\u6700\u540e\u62b5\u6d88<\/li>\n<\/ul>\n<\/li>\n<li>Dinic\u7b97\u6cd5\n<ul>\n<li>\u57fa\u672c\u601d\u60f3<\/li>\n<li>\u8bbe\u8ba1\u7a0b\u5e8f<\/li>\n<li>\u4ee3\u7801\u5b9e\u73b0<\/li>\n<li>\u53e6\u4e00\u79cd\u4ee3\u7801\u5b9e\u73b0<\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n<\/div>\n<h2 id=\"\u95ee\u9898\u5b9a\u4e49\">\u95ee\u9898\u5b9a\u4e49<\/h2>\n<p>\u7ed9\u5b9a\u6709\u5411\u56feG=(V,E)\uff0c\u5176\u6bcf\u6761\u8fb9\u90fd\u6709\u5bb9\u91cf<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-28-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-72\" style=\"width: 1.878em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.565em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.565em, 1001.57em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-73\"><span class=\"msubsup\" id=\"MathJax-Span-74\"><span style=\"display: inline-block; position: relative; width: 1.565em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.44em, 1000.42em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-75\" style=\"font-family: MathJax_Math-italic;\">c<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.419em;\"><span class=\"texatom\" id=\"MathJax-Span-76\"><span class=\"mrow\" id=\"MathJax-Span-77\"><span class=\"mi\" id=\"MathJax-Span-78\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-79\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-80\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">w<\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.003em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> c v , w <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-28\">c_{v,w}<\/script>.\u8fd9\u4e2a\u5bb9\u91cf\u4ee3\u8868\u8fd9\u4e2a\u8fb9\u53ef\u4ee5\u901a\u8fc7\u7684\u6700\u5927\u5bb9\u91cf\u3002\u5bf9\u4e8e\u4efb\u4e00\u6761\u8fb9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-29-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-81\" style=\"width: 2.919em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.398em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1002.29em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-82\"><span class=\"mo\" id=\"MathJax-Span-83\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-84\" style=\"font-family: MathJax_Math-italic;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-85\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-86\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">w<\/span><span class=\"mo\" id=\"MathJax-Span-87\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( v , w ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-29\">(v,w)<\/script>\uff0c\u5728\u4ecev\u5230w\u7684\u65b9\u5411\u4e0a\uff0c\u6700\u591a\u6709<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-30-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-88\" style=\"width: 1.878em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.565em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.565em, 1001.57em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-89\"><span class=\"msubsup\" id=\"MathJax-Span-90\"><span style=\"display: inline-block; position: relative; width: 1.565em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.44em, 1000.42em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-91\" style=\"font-family: MathJax_Math-italic;\">c<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.419em;\"><span class=\"texatom\" id=\"MathJax-Span-92\"><span class=\"mrow\" id=\"MathJax-Span-93\"><span class=\"mi\" id=\"MathJax-Span-94\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-95\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-96\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">w<\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.003em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> c v , w <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-30\">c_{v,w}<\/script>\u4e2a\u5355\u4f4d\u7684\u6d41\u53ef\u4ee5\u901a\u8fc7\u3002\u6ce8\u610f\u5bb9\u91cf\u4e5f\u662f\u5177\u6709\u65b9\u5411\u7684\u3002 <br \/> \u56fe\u4e2d\u6709\u4e24\u4e2a\u7279\u6b8a\u70b9\uff0c\u4e00\u4e2a\u662fs\uff0c\u79f0\u4e3a\u6e90\u70b9\uff08source\uff09\uff0c\u4e00\u4e2a\u662ft\uff0c\u79f0\u4e3a\u6536\u70b9\uff08sink\uff09\u3002 <br \/> \u65e2\u4e0d\u662f\u6e90\u70b9\u4e5f\u4e0d\u662f\u6536\u70b9\u7684\u70b9\uff0c\u603b\u7684\u8fdb\u5165\u7684\u6d41\u5fc5\u987b\u7b49\u4e8e\u603b\u7684\u53d1\u51fa\u7684\u6d41\u3002 <br \/> <strong>\u6700\u5927\u6d41\u95ee\u9898\u5c31\u662f\u786e\u5b9a\u4eces\u5230t\u53ef\u4ee5\u901a\u8fc7\u7684\u6700\u5927\u6d41\u91cf\u3002<\/strong> <br \/> \u95ee\u9898\u5bf9\u4e8e\u6709\u73af\u65e0\u73af\u5e76\u6ca1\u6709\u8981\u6c42\uff0c\u6240\u4ee5\u7b97\u6cd5\u5fc5\u987b\u4e5f\u80fd\u89e3\u51b3\u6709\u73af\u7684\u60c5\u51b5\u3002<\/p>\n<h2 id=\"\u9650\u5236\u6761\u4ef6\">\u9650\u5236\u6761\u4ef6<\/h2>\n<p>\u5bf9\u4e8e\u4efb\u4e00\u6761\u8fb9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-31-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-97\" style=\"width: 2.919em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.398em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1002.29em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-98\"><span class=\"mo\" id=\"MathJax-Span-99\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-100\" style=\"font-family: MathJax_Math-italic;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-101\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-102\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">w<\/span><span class=\"mo\" id=\"MathJax-Span-103\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( v , w ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-31\">(v,w)<\/script>\uff0c\u5728\u5176\u4e0a\u8fd0\u884c\u7684\u6d41\u7684\u6d41\u91cf\u5fc5\u987b&lt;=<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-32-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-104\" style=\"width: 1.878em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.565em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.565em, 1001.57em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-105\"><span class=\"msubsup\" id=\"MathJax-Span-106\"><span style=\"display: inline-block; position: relative; width: 1.565em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.44em, 1000.42em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-107\" style=\"font-family: MathJax_Math-italic;\">c<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.419em;\"><span class=\"texatom\" id=\"MathJax-Span-108\"><span class=\"mrow\" id=\"MathJax-Span-109\"><span class=\"mi\" id=\"MathJax-Span-110\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-111\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-112\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">w<\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.003em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> c v , w <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-32\">c_{v,w}<\/script> <br \/> \u5bf9\u4e8e\u4efb\u4e00\u8282\u70b9\uff0c\u603b\u7684\u8fdb\u5165\u7684\u6d41\u5fc5\u987b\u7b49\u4e8e\u603b\u7684\u53d1\u51fa\u7684\u6d41\uff08\u9664\u4e86\u6e90\u70b9\u3001\u6536\u70b9\uff09<\/p>\n<h2 id=\"\u793a\u4f8b\">\u793a\u4f8b<\/h2>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725201914363\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c1\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c1\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u5982\u4e0a\u56fe\u6240\u793a\uff0c\u5de6\u8fb9\u662f\u4e3a\u4e00\u4e2a\u56fe\uff0c\u53f3\u8fb9\u4e3a\u8be5\u56fe\u7684\u6700\u5927\u6d41\u793a\u610f\u56fe\u3002 <br \/> \u5b9e\u9645\u5de6\u8fb9\u7684\u56fe\uff0c\u6bcf\u6761\u8fb9\u4e0a\u7684\u6570\u5b57\u65e2\u4ee3\u8868\u4e86\u8fd9\u6761\u8fb9\u7684\u5bb9\u91cf\uff0c\u4e5f\u4ee3\u8868\u4e86\u8fd9\u6761\u8fb9\u7684\u521d\u59cb\u6d41\u91cf\uff0c\u4f46\u8fd9\u4e2a\u521d\u59cb\u6d41\u91cf\u5b9e\u9645\u4e0a\u662f\u4e0d\u80fd\u90fd\u8fbe\u5230\u7684\uff0c\u56e0\u4e3a\u9650\u5236\u6761\u4ef6\uff08\u603b\u7684\u8fdb\u5165\u7684\u6d41\u5fc5\u987b\u7b49\u4e8e\u603b\u7684\u53d1\u51fa\u7684\u6d41\uff09\uff0c<strong>\u6240\u4ee5\u95ee\u9898\u9700\u8981\u6211\u4eec\u627e\u5230\u8fd9\u4e2a\u56fe\u7684\u5b9e\u9645\u6d41\u91cf\u5230\u8fbe\u90fd\u662f\u591a\u5c11\uff0c\u4e14\u8fd8\u8981\u6c42\u4eces\u5230t\u901a\u8fc7\u6700\u5927\u6d41\u91cf\u3002<\/strong> <br \/> \u4ece\u4e0a\u56fe\u4e2d\u597d\u50cf\u5f88\u5bb9\u6613\u5c31\u53d1\u73b0\u4e86\u6700\u5927\u6d41\u4e3a5\uff0c\u56e0\u4e3a\u76f4\u63a5\u770b\u6e90\u70b9\u6216\u8005\u6536\u70b9\u7684\u603b\u6d41\u91cf\u5c31\u662f5.\u4f46\u4e0b\u9762\u8fd9\u4e2a\u56fe\u5c31\u4e0d\u80fd\u76f4\u63a5\u770b\u51fa\u4e86\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725204232513\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c2\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c2\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u5982\u4e0a\u56fe\u6240\u793a\uff0c\u5982\u679c\u53ea\u770b\u6e90\u70b9\u6216\u8005\u6536\u70b9\uff0c\u90a3\u4e48\u4f60\u53ef\u80fd\u4f1a\u89c9\u5f97\u6700\u5927\u6d41\u4e3a6\uff0c\u4f46\u5b9e\u9645\u4e0a\u6700\u5927\u6d41\u4e3a5. <br \/> \u5de6\u56fe\u7684\u865a\u7ebf\u5207\u5206\u5c31\u8bc1\u660e\u4e86\u8be5\u56fe\u7684\u6700\u5927\u6d41\u4e3a5\uff0c\u76f4\u89c2\u4e0a\u6765\u770b\uff0c\u865a\u7ebf\u5207\u5206\u7684\u4e24\u6761\u8fb9\u52a0\u8d77\u6765\u7684\u548c\u5c31\u4e3a5. <br \/> <strong>\u5207\u5206\u8981\u6c42<\/strong>\uff1a\u5c06\u56fe\u5207\u5206\u6210\u4e24\u90e8\u5206\uff0c\u4e00\u90e8\u5206\u5305\u62ecs\u548c\u5176\u4ed6\u4e00\u4e9b\u9876\u70b9\uff1b\u53e6\u4e00\u90e8\u5206\u5305\u62ect\u548c\u5176\u4ed6\u4e00\u4e9b\u9876\u70b9\u3002\u5e76\u4e14\u5207\u5206\u5230\u7684\u8fb9\uff0c\u6bd4\u5982\u8fd9\u91cc\u7684\u8fb9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-33-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-113\" style=\"width: 5.159em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 4.273em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1004.17em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-114\"><span class=\"mo\" id=\"MathJax-Span-115\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-116\" style=\"font-family: MathJax_Math-italic;\">a<\/span><span class=\"mo\" id=\"MathJax-Span-117\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-118\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">c<\/span><span class=\"mo\" id=\"MathJax-Span-119\" style=\"font-family: MathJax_Main;\">)<\/span><span class=\"mo\" id=\"MathJax-Span-120\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-121\" style=\"font-family: MathJax_Math-italic;\">d<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.003em;\"><\/span><\/span><span class=\"mo\" id=\"MathJax-Span-122\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-123\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">t<\/span><span class=\"mo\" id=\"MathJax-Span-124\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( a , c ) ( d , t ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-33\">(a,c)(d,t)<\/script>\uff0c\u8981\u8ba9\u8fb9\u7684\u524d\u9a71\u5728s\u5206\u533a\uff0c\u8fb9\u7684\u540e\u7ee7\u5728t\u5206\u533a\u3002\u8fd9\u6837\u7684\u5207\u5206\u4e00\u822c\u6709\u591a\u79cd\u60c5\u51b5\uff0c\u5177\u6709\u6700\u5c0f\u603b\u5bb9\u91cf\u7684\u5207\u5206\u4fbf\u662f\u7ed9\u51fa\u6700\u5927\u6d41\u3002<\/p>\n<h2 id=\"\u57fa\u672c\u601d\u60f3\">\u57fa\u672c\u601d\u60f3<\/h2>\n<p>\u9996\u8981\u60f3\u6cd5\u662f\u5206\u9636\u6bb5\u8fdb\u884c\u3002\u4ece\u539f\u56fe<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-34-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-125\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.784em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1000.78em, 2.294em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-126\"><span class=\"mi\" id=\"MathJax-Span-127\" style=\"font-family: MathJax_Math-italic;\">G<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 1.003em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-34\">G<\/script>\u6784\u9020\u4e00\u4e2a\u6d41\u56fe<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-35-Frame\" tabindex=\"0\" style=\"position: relative;\" data-mathml=\"<math xmlns=&quot;http:\/\/www.w3.org\/1998\/Math\/MathML&quot;><msub><mi>G<\/mi><mi>f<\/mi><\/msub><\/math>\" role=\"presentation\"><br \/>\n  <nobr aria-hidden=\"true\"><br \/>\n   <span class=\"math\" id=\"MathJax-Span-128\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-129\"><span class=\"msubsup\" id=\"MathJax-Span-130\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-131\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-132\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span><br \/>\n  <\/nobr><span class=\"MJX_Assistive_MathML\" role=\"presentation\"><br \/>\n   <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"> \n    <msub> \n     <mi>\n       G \n     <\/mi> \n     <mi>\n       f \n     <\/mi> \n    <\/msub> \n   <\/math><\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-35\">G_f<\/script>\u3002<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-36-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-133\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-134\"><span class=\"msubsup\" id=\"MathJax-Span-135\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-136\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-137\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G f <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-36\">G_f<\/script>\u4ee3\u8868\u7b97\u6cd5\u5728\u4efb\u610f\u9636\u6bb5\u5df2\u7ecf\u5230\u8fbe\u7684\u6d41\u3002\u5f00\u59cb\u65f6<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-37-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-138\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-139\"><span class=\"msubsup\" id=\"MathJax-Span-140\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-141\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-142\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G f <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-37\">G_f<\/script>\u6240\u6709\u7684\u8fb9\u90fd\u6ca1\u6709\u6d41\uff0c\u6211\u4eec\u5e0c\u671b\u7b97\u6cd5\u7ec8\u6b62\u65f6<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-38-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-143\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-144\"><span class=\"msubsup\" id=\"MathJax-Span-145\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-146\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-147\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G f <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-38\">G_f<\/script>\u5305\u62ec\u6700\u5927\u6d41\u3002 <br \/> \u8fd8\u6784\u9020\u4e00\u4e2a\u56fe<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-39-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-148\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-149\"><span class=\"msubsup\" id=\"MathJax-Span-150\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-151\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-152\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-39\">G_r<\/script>\uff0c\u79f0\u4e3a\u6b8b\u4f59\u56fe\uff08residual graph\uff09\uff0c\u8868\u793a\u5728<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-40-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-153\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-154\"><span class=\"msubsup\" id=\"MathJax-Span-155\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-156\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-157\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G f <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-40\">G_f<\/script>\u4e0a\u6bcf\u6761\u8fb9\u8fd8\u80fd\u518d\u6dfb\u52a0\u4e0a\u591a\u5c11\u6d41\u3002\u5f00\u59cb\u65f6<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-41-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-158\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-159\"><span class=\"msubsup\" id=\"MathJax-Span-160\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-161\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-162\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-41\">G_r<\/script>\u5c31\u7b49\u4e8e\u539f\u56fe<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-42-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-163\" style=\"width: 0.94em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 0.784em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1000.78em, 2.294em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-164\"><span class=\"mi\" id=\"MathJax-Span-165\" style=\"font-family: MathJax_Math-italic;\">G<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.059em; border-left: 0px solid; width: 0px; height: 1.003em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-42\">G<\/script>\u3002 <br \/> \u6bcf\u5f53\u6211\u4eec\u5bf9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-43-Frame\" tabindex=\"0\" style=\"position: relative;\" data-mathml=\"<math xmlns=&quot;http:\/\/www.w3.org\/1998\/Math\/MathML&quot;><msub><mi>G<\/mi><mi>f<\/mi><\/msub><\/math>\" role=\"presentation\"><br \/>\n  <nobr aria-hidden=\"true\"><br \/>\n   <span class=\"math\" id=\"MathJax-Span-166\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-167\"><span class=\"msubsup\" id=\"MathJax-Span-168\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-169\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-170\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span><br \/>\n  <\/nobr><span class=\"MJX_Assistive_MathML\" role=\"presentation\"><br \/>\n   <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"> \n    <msub> \n     <mi>\n       G \n     <\/mi> \n     <mi>\n       f \n     <\/mi> \n    <\/msub> \n   <\/math><\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-43\">G_f<\/script>\u91cc\u9762\u7684\u8fb9\u6dfb\u52a0\u6d41\u65f6\uff0c\u5c31\u4f1a\u5bf9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-44-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-171\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-172\"><span class=\"msubsup\" id=\"MathJax-Span-173\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-174\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-175\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-44\">G_r<\/script>\u91cc\u540c\u6837\u7684\u8fb9\u51cf\u5c0f\u6d41\u3002<\/p>\n<p>\u5728\u6bcf\u4e2a\u9636\u6bb5\uff0c\u6211\u4eec\u5bfb\u627e<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-45-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-176\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-177\"><span class=\"msubsup\" id=\"MathJax-Span-178\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-179\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-180\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-45\">G_r<\/script>\u4e2d\u4eces\u5230t\u7684\u4e00\u6761\u8def\u5f84\uff0c\u79f0\u4f5c\u589e\u5e7f\u8def\u5f84\uff08augmenting path\uff09\u3002\u589e\u5e7f\u8def\u5f84\u4e0a\u6240\u6709\u8fb9\u7684\u6700\u5c0f\u6743\u503c\u5c31\u662f\u53ef\u4ee5\u6dfb\u52a0\u8def\u5f84\u4e0a\u6240\u6709\u8fb9\u7684\u6d41\u7684\u91cf\u3002\u6211\u4eec\u901a\u8fc7\u4e0d\u65ad\u51cf\u5c0f<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-46-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-181\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-182\"><span class=\"msubsup\" id=\"MathJax-Span-183\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-184\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-185\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-46\">G_r<\/script>\u7684\u6d41\uff0c\u589e\u52a0<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-47-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-186\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-187\"><span class=\"msubsup\" id=\"MathJax-Span-188\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-189\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-190\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G f <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-47\">G_f<\/script>\u7684\u6d41\u6765\u6267\u884c\u7b97\u6cd5\u3002 <br \/> <strong>\u5f53\u53d1\u73b0\u5728<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-48-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-191\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-192\"><span class=\"msubsup\" id=\"MathJax-Span-193\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-194\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-195\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-48\">G_r<\/script>\u4e2d\u6ca1\u6709\u4e86\u4eces\u5230t\u7684\u8def\u5f84\u65f6\uff0c\u7b97\u6cd5\u505c\u6b62\u3002<\/strong> <br \/> \u4f46\u8fd9\u79cd\u601d\u8def\uff0c\u6709\u53ef\u80fd\u4f1a\u8ba9\u7b97\u6cd5\u627e\u4e0d\u5230\u6700\u4f18\u89e3\uff0c\u56e0\u4e3a\u6bcf\u6b21\u9009\u62e9\u589e\u5e7f\u8def\u5f84\u4e0d\u4e00\u5b9a\u90fd\u662f\u6700\u597d\u7684\u9009\u62e9\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725210804121\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c3\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c3\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u5982\u4e0a\u56fe\uff0c\u5de6\u8fb9\u4e3a<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-49-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-196\" style=\"width: 1.513em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.25em, 2.607em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-197\"><span class=\"msubsup\" id=\"MathJax-Span-198\"><span style=\"display: inline-block; position: relative; width: 1.253em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-199\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-200\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.434em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G f <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-49\">G_f<\/script>\uff0c\u53f3\u8fb9\u4e3a<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-50-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-201\" style=\"width: 1.461em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1001.2em, 2.451em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-202\"><span class=\"msubsup\" id=\"MathJax-Span-203\"><span style=\"display: inline-block; position: relative; width: 1.201em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.128em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-204\" style=\"font-family: MathJax_Math-italic;\">G<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -3.852em; left: 0.784em;\"><span class=\"mi\" id=\"MathJax-Span-205\" style=\"font-size: 70.7%; font-family: MathJax_Math-italic;\">r<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.247em; border-left: 0px solid; width: 0px; height: 1.191em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> G r <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-50\">G_r<\/script>\u3002\u73b0\u5728\u4e3a\u521d\u59cb\u72b6\u6001\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725211021307\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c4\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c4\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u9009\u62e9\u4e86\u589e\u5e7f\u8def\u5f84\u4e3as,b,d,t\u3002\u4e00\u65e6\u6d88\u8017\u5149\u4e86\u6b8b\u4f59\u56fe\u7684\u67d0\u6761\u8fb9\u7684\u6d41\u91cf\uff0c\u6b8b\u4f59\u56fe\u91cc\u5c31\u9700\u8981\u53bb\u6389\u8fd9\u6761\u8fb9\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/2018072521124152\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c5\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c5\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u9009\u62e9\u4e86\u589e\u5e7f\u8def\u5f84\u4e3as,a,c,t\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725211345302\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c6\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c6\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u6700\u597d\u9009\u62e9\u4e86\u589e\u5e7f\u8def\u5f84\u4e3as,a,d,t\u3002\u7b97\u6cd5\u7ec8\u6b62\uff0c\u56e0\u4e3a\u6ca1\u6709\u8def\u5f84\u80fd\u4eces\u5230t\u4e86\u3002<\/p>\n<h2 id=\"\u5f15\u5165\u53cd\u5411\u8fb9\">\u5f15\u5165\u53cd\u5411\u8fb9<\/h2>\n<p>\u5982\u679c\u4e0a\u8ff0\u8fc7\u7a0b\uff0c\u4ece\u521d\u59cb\u60c5\u51b5\uff0c\u6211\u4eec\u9009\u62e9\u8def\u5f84s,a,d,t\uff0c\u8fd9\u6761\u8def\u5f84\u867d\u7136\u80fd\u67093\u7684\u6700\u5c0f\u6d41\u91cf\uff0c\u597d\u50cf\u662f\u4e00\u79cd\u4e0d\u9519\u7684\u9009\u62e9\u3002\u4f46\u8fd9\u6837\u9009\u62e9\u540e\uff0c\u5374\u8ba9\u7b97\u6cd5\u76f4\u63a5\u7ec8\u6b62\u4e86\uff0c\u56e0\u4e3a\u6ca1\u6709\u589e\u5e7f\u8def\u5f84\u4e86\u3002\u8fd9\u5c31\u8868\u793a\u8d2a\u5a6a\u7b97\u6cd5\u884c\u4e0d\u901a\u3002\u5931\u8d25\u539f\u56e0\u5982\u4e0b\u56fe\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725212020769\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c7\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c7\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u4e3a\u4e86\u5f97\u5230\u6700\u4f18\u89e3\uff0c\u6211\u4eec\u9700\u8981\u80fd\u8ba9\u7b97\u6cd5\u64a4\u9500\u51b3\u5b9a\uff0c\u5982\u679c\u6211\u4eec\u4e4b\u524d\u4f5c\u51fa\u4e86\u9519\u8bef\u51b3\u5b9a\u7684\u8bdd\u3002 <br \/> <font color=\"red\">\u6240\u4ee5\uff0c\u5728\u7b97\u6cd5\u7684\u6bcf\u4e2a\u9636\u6bb5\uff0c\u4fee\u6539\u6b8b\u4f59\u56fe\u65f6\uff0c\u6839\u636e\u589e\u5e7f\u8def\u5f84\u51cf\u5c0f\u76f8\u5e94\u7684\u6d41\u65f6\uff08\u589e\u5e7f\u8def\u5f84\u7684\u6d41\u4e3af\uff09\uff0c\u8fd8\u8981\u5bf9\u589e\u5e7f\u8def\u5f84\u7684\u6bcf\u6761\u8fb9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-51-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-206\" style=\"width: 2.919em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.398em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1002.29em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-207\"><span class=\"mo\" id=\"MathJax-Span-208\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-209\" style=\"font-family: MathJax_Math-italic;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-210\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-211\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">w<\/span><span class=\"mo\" id=\"MathJax-Span-212\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( v , w ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-51\">(v,w)<\/script>\u7684\u53cd\u5411\u8fb9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-52-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-213\" style=\"width: 2.919em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.398em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1002.29em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-214\"><span class=\"mo\" id=\"MathJax-Span-215\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-216\" style=\"font-family: MathJax_Math-italic;\">w<\/span><span class=\"mo\" id=\"MathJax-Span-217\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-218\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">v<\/span><span class=\"mo\" id=\"MathJax-Span-219\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( w , v ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-52\">(w,v)<\/script>\u6dfb\u52a0\u4e00\u6761\u5bb9\u91cf\u4e3af\u7684\u8fb9\u3002 <br \/> \u8fd9\u6837\u505a\u7684\u6548\u679c\u5c31\u662f\uff0c\u6211\u4eec\u80fd\u4ee5\u76f8\u53cd\u7684\u65b9\u5411\uff0c\u518d\u8d70\u4e00\u904d\u4e4b\u524d\u8d70\u8fc7\u7684\u6d41\u3002\u5373\u80fd\u4f7f\u7b97\u6cd5\u64a4\u9500\u4e4b\u524d\u505a\u7684\u51b3\u5b9a\u3002<\/font> <br \/> \u4e0b\u9762\u7684\u793a\u4f8b\u8bf4\u660e\u4e86\u53cd\u5411\u8fb9\u7684\u4f5c\u7528\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725214057324\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c8\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c8\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u7b2c\u4e00\u6b21\u9009\u62e9\u8def\u5f84s,a,d,t\u3002\u5e76\u4e14\u5411\u6b8b\u4f59\u56fe\u6dfb\u52a0\u53cd\u5411\u8fb9\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725213129835\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c9\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c9\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u7b2c\u4e8c\u6b21\u9009\u62e9\u8def\u5f84s,b,d,a,c,t\u3002\u5176\u4e2d\u4eced\u5230a\uff0c\u5c31\u8d70\u4e86\u4e0a\u4e00\u6b65\u8d70\u7684\u53cd\u65b9\u5411\u7684\u6d41\uff0c\u901a\u8fc7\u8fd9\u6837\u6765\u8ba9\u7b97\u6cd5\u53cd\u6094\u51b3\u5b9a\u3002\u6ca1\u6709\u4e86\u589e\u5e7f\u8def\u5f84\uff0c\u7b97\u6cd5\u505c\u6b62\u3002<\/p>\n<p><font color=\"red\">\u53cd\u5411\u8fb9\u662f\u7b97\u6cd5\u7684\u7cbe\u534e\u90e8\u5206\u6240\u5728\uff0c\u672c\u6765\u7b2c\u4e00\u6b65\u65f6\u8fb9<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-53-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-220\" style=\"width: 2.711em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.242em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1002.14em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-221\"><span class=\"mo\" id=\"MathJax-Span-222\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-223\" style=\"font-family: MathJax_Math-italic;\">d<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.003em;\"><\/span><\/span><span class=\"mo\" id=\"MathJax-Span-224\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-225\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">a<\/span><span class=\"mo\" id=\"MathJax-Span-226\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( d , a ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-53\">(d,a)<\/script>\u7684\u6d41\u4e3a3\uff08\u8fd9\u662f\u7b2c\u4e00\u6b21\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u4ea7\u751f\u7684\u53cd\u5411\u8fb9\uff09\uff0c\u4f46\u7b2c\u4e8c\u6b65\u7531\u4e8e\u589e\u5e7f\u8def\u5f84\u7684\u9009\u62e9\u5bfc\u81f4<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-54-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-227\" style=\"width: 2.711em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 2.242em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.253em, 1002.14em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-228\"><span class=\"mo\" id=\"MathJax-Span-229\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-230\" style=\"font-family: MathJax_Math-italic;\">d<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.003em;\"><\/span><\/span><span class=\"mo\" id=\"MathJax-Span-231\" style=\"font-family: MathJax_Main;\">,<\/span><span class=\"mi\" id=\"MathJax-Span-232\" style=\"font-family: MathJax_Math-italic; padding-left: 0.159em;\">a<\/span><span class=\"mo\" id=\"MathJax-Span-233\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.316em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> ( d , a ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-54\">(d,a)<\/script>\u7684\u6d41\u88ab\u62b5\u6d88\u6389\u4e862\u5355\u4f4d\u7684\u6d41\u3002 <br \/> \u4e3a\u4ec0\u4e48\u52a0\u53cd\u5411\u8fb9\u4e0d\u4f1a\u6709\u574f\u7684\u5f71\u54cd\u5462\uff0c\u56e0\u4e3a\u5b83\u7684\u65b9\u5411\u662f\u4ecet\u5230s\u7684\uff0c\u662f\u53cd\u65b9\u5411\u7684\uff0c\u52a0\u4e86\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u4e5f\u4e0d\u53ef\u80fd\u51fa\u9519\u3002\u4f46\u52a0\u4e86\u4ee5\u540e\uff0c\u5374\u8ba9\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u6709\u4e86\u66f4\u591a\u7684\u9009\u62e9\u5373\u56de\u9000\u7684\u9009\u62e9\u3002<\/font> <br \/> <font color=\"blue\">\u56de\u9000\u7684\u610f\u601d\u5176\u5b9e\u5c31\u662f\uff0c\u7b2c\u4e8c\u6b21\u9009\u62e9\u7684\u589e\u5e7f\u8def\u5f84\uff0c\u53ef\u4ee5\u62b5\u6d88\u6389\u7b2c\u4e00\u6b21\u9009\u62e9\u7684\u589e\u5e7f\u8def\u5f84\u7684\u6d41\uff08\u8fd9\u91cc\u6307\u7684\u6700\u5927\u6d41\u56fe\uff09<\/font><\/p>\n<h2 id=\"edmond-karp\u7b97\u6cd5\">Edmond-Karp\u7b97\u6cd5<\/h2>\n<p>\u4ee3\u7801\u90e8\u5206\u53c2\u8003\u4e86\u7f51\u7edc\u6d41\u2014\u6700\u5927\u6d41\uff08Edmond-Karp\u7b97\u6cd5\uff09\uff0c\u7528python3\u8fdb\u884c\u4e86\u5b9e\u73b0\u3002 <br \/> \u4f7f\u7528\u7684\u56fe\u5c31\u662f\u672c\u6587\u7b2c\u4e00\u4e2a\u56fe\u7684\u5de6\u8fb9\u7684\u56fe\u3002<\/p>\n<pre class=\"prettyprint\"><code class=\"language-python hljs \"><span class=\"hljs-keyword\">from<\/span> queue <span class=\"hljs-keyword\">import<\/span> Queue <span class=\"hljs-comment\">#n #\u8fb9\u7684\u4e2a\u6570<\/span> m = <span class=\"hljs-number\">6<\/span><span class=\"hljs-comment\">#\u70b9\u7684\u4e2a\u6570<\/span> residual = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u6b8b\u4f59\u56fe\u7684\u5269\u4f59\u6d41\u91cf<\/span> maxflowgraph = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\u56fe\uff0c\u521d\u59cb\u90fd\u4e3a0<\/span> flow = [<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u524d\u8fdb\u8fc7\u7a0b\u8bb0\u5f55\u7684\u6700\u5c0f\u6d41\u91cf<\/span> pre = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u6bcf\u4e2a\u8282\u70b9\u7684\u524d\u9a71<\/span> q = Queue() <span class=\"hljs-comment\">#\u961f\u5217\uff0c\u7528\u4e8eBFS\u5730\u5bfb\u627e\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-comment\">#\u8bbe\u7f6e\u521d\u59cb\u56fe\u7684\u6d41\u91cf\u8d70\u5411<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">1<\/span>]=<span class=\"hljs-number\">3<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">1<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">3<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">4<\/span> residual[<span class=\"hljs-number\">2<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">3<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">3<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">BFS<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> q.empty()<span class=\"hljs-comment\">#\u6e05\u7a7a\u961f\u5217<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): pre[i] = float(<span class=\"hljs-string\">'inf'<\/span>) flow[source] = float(<span class=\"hljs-string\">'inf'<\/span>)<span class=\"hljs-comment\">#\u8fd9\u91cc\u8981\u662f\u4e0d\u6539\uff0c\u90a3\u4e48\u627e\u5230\u7684\u8def\u5f84\u7684\u6d41\u91cf\u6c38\u8fdc\u662f0<\/span> <span class=\"hljs-comment\">#\u4e0d\u7528\u5c06flow\u7684\u5176\u4ed6\u6e05\u96f6<\/span> q.put(source) <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">not<\/span> q.empty()): index = q.get() <span class=\"hljs-keyword\">if<\/span>(index == sink): <span class=\"hljs-keyword\">break<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i!=source) &amp; (residual[index][i]&gt;<span class=\"hljs-number\">0<\/span>) &amp; (pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>)) ): <span class=\"hljs-comment\">#i!=source\uff0c\u4ecesource\u5230source\u4e0d\u7528\u5206\u6790\u4e86<\/span> <span class=\"hljs-comment\">#residual[index][i]&gt;0\uff0c\u8fb9\u4e0a\u6709\u6d41\u91cf\u53ef\u4ee5\u8d70<\/span> <span class=\"hljs-comment\">#pre[i]==float('inf')\uff0c\u4ee3\u8868BFS\u8fd8\u6ca1\u6709\u5ef6\u4f38\u5230\u8fd9\u4e2a\u70b9\u4e0a<\/span> pre[i] = index flow[i] = min(flow[index],residual[index][i]) q.put(i) <span class=\"hljs-keyword\">if<\/span>(pre[sink] == float(<span class=\"hljs-string\">'inf'<\/span>)): <span class=\"hljs-comment\">#\u6c47\u70b9\u7684\u524d\u9a71\u8fd8\u662f\u521d\u59cb\u503c\uff0c\u8bf4\u660e\u5df2\u65e0\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-keyword\">return<\/span> -<span class=\"hljs-number\">1<\/span> <span class=\"hljs-keyword\">else<\/span>: <span class=\"hljs-keyword\">return<\/span> flow[sink] <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">maxflow<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> sumflow = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\uff0c\u4e00\u76f4\u7d2f\u52a0<\/span> augmentflow = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u5f53\u524d\u5bfb\u627e\u5230\u7684\u589e\u5e7f\u8def\u5f84\u7684\u6700\u5c0f\u901a\u8fc7\u6d41\u91cf<\/span> <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">True<\/span>): augmentflow = BFS(source,sink) <span class=\"hljs-keyword\">if<\/span>(augmentflow == -<span class=\"hljs-number\">1<\/span>): <span class=\"hljs-keyword\">break<\/span><span class=\"hljs-comment\">#\u8fd4\u56de-1\u8bf4\u660e\u5df2\u6ca1\u6709\u589e\u5e7f\u8def\u5f84<\/span> k = sink <span class=\"hljs-keyword\">while<\/span>(k!=source):<span class=\"hljs-comment\">#k\u56de\u6eaf\u5230\u8d77\u70b9\uff0c\u505c\u6b62<\/span> prev = pre[k]<span class=\"hljs-comment\">#\u8d70\u7684\u65b9\u5411\u662f\u4eceprev\u5230k<\/span> maxflowgraph[prev][k] += augmentflow residual[prev][k] -= augmentflow<span class=\"hljs-comment\">#\u524d\u8fdb\u65b9\u5411\u6d88\u8017\u6389\u4e86<\/span> residual[k][prev] += augmentflow<span class=\"hljs-comment\">#\u53cd\u5411\u8fb9<\/span> k = prev sumflow += augmentflow <span class=\"hljs-keyword\">return<\/span> sumflow result = maxflow(<span class=\"hljs-number\">0<\/span>,m-<span class=\"hljs-number\">1<\/span>) print(result) print(maxflowgraph)<span class=\"hljs-comment\">#\u6700\u5927\u6d41\u56fe<\/span><\/code><\/pre>\n<p>BFS\u51fd\u6570\u7528\u6765\u9009\u62e9\u589e\u5e7f\u8def\u5f84\uff0c\u6bcf\u5f53\u5bfb\u627e\u5230\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u5c31\u5bf9\u6b8b\u4f59\u56fe\u548c\u6700\u5927\u6d41\u56fe\u4f5c\u76f8\u5e94\u7684\u4fee\u6539\u3002\u8fd0\u884c\u7ed3\u679c\u5982\u4e0b\uff1a5\u4ee3\u8868\u6700\u5927\u6d41\u5927\u5c0f\uff1b\u4e8c\u7ef4list\u4ee3\u8868\u6700\u5927\u6d41\u56fe\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180725215807434\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c10\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c10\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u793a\u610f\u56fe\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726123941688\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c11\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c11\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u6709\u73af\u8fd9\u4e2a\u7b97\u6cd5\u4e5f\u80fd\u6267\u884c\uff0c\u5c06\u8fd9\u884c\u4ee3\u7801<code>residual[1][4]=4<\/code>\u6539\u4e3a<code>residual[4][1]=4<\/code>\uff0c\u6b64\u65f6\u51fa\u73b0\u73af\uff0c\u4ece1\u52302\u52304\u7684\u73af\u3002\u8fd0\u884c\u7ed3\u679c\u4e3a\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726124247972\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c12\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c12\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u793a\u610f\u56fe\u5982\u4e0b\uff1a\u539f\u56fe\u4e2d\uff0c\u6a59\u8272\u7bad\u5934\u5c31\u662f\u5f62\u6210\u7684\u73af <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180727125314524\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c13\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c13\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" ><\/p>\n<h2 id=\"ford-fulkerson\u7b97\u6cd5\">Ford-Fulkerson\u7b97\u6cd5<\/h2>\n<p>\u9996\u5148\u9644\u4e0ageeksforgeeks\u7684\u53cb\u60c5\u94fe\u63a5Ford-Fulkerson Algorithm for Maximum Flow Problem\uff0c\u867d\u7136\u662f\u82f1\u6587\u7684\uff0c\u4f46\u8bb2\u5f97\u633a\u597d\u7684\u3002<\/p>\n<blockquote>\n<p>The above implementation of Ford Fulkerson Algorithm is called Edmonds-Karp Algorithm. The idea of Edmonds-Karp is to use BFS in Ford Fulkerson implementation as BFS always picks a path with minimum number of edges. When BFS is used, the worst case time complexity can be reduced to O(VE2). The above implementation uses adjacency matrix representation though where BFS takes O(V2) time, the time complexity of the above implementation is O(EV3) (Refer CLRS book for proof of time complexity)<\/p>\n<\/blockquote>\n<p>\u4e0a\u9762\u8fd9\u6bb5\u8bdd\u6765\u81ea\u53cb\u60c5\u94fe\u63a5\u3002\u610f\u601d\u5c31\u662f\uff0cFord-Fulkerson\u7b97\u6cd5\u5176\u5b9e\u5c31\u662f\u4e00\u79cd\u601d\u60f3\uff0c\u4e0d\u662f\u4e00\u79cd\u5177\u4f53\u7684\u5b9e\u73b0\u3002\u800c<strong>Edmonds-Karp\u7b97\u6cd5\u662f\u5bf9Ford-Fulkerson\u7b97\u6cd5\u7684\u4e00\u79cd\u5b9e\u73b0\uff0c\u5b9e\u73b0\u7684\u7279\u70b9\u5c31\u5728\uff0c\u5728\u9009\u62e9\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u91c7\u7528BFS\u7684\u65b9\u6cd5\u5bfb\u627e<\/strong>\u3002Ford-Fulkerson\u7b97\u6cd5\u53ea\u662f\u4e00\u79cd\u601d\u60f3\u7684\u539f\u56e0\u5c31\u5728\u4e8e\uff0c\u5b83\u5e76\u6ca1\u6709\u786e\u5b9a\u4e0b\u6765\uff0c\u5bfb\u627e\u589e\u52a0\u8def\u5f84\u65f6\uff0c\u5230\u8fbe\u91c7\u7528\u4ec0\u4e48\u65b9\u6cd5\uff0c\u6bd4\u5982\u53ef\u4ee5BFS\uff0cDFS\uff0c\u8d2a\u5fc3\u7b49\u7b49\u3002 <br \/> \u53cb\u60c5\u94fe\u63a5\u7684python\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre class=\"prettyprint\"><code class=\" hljs python\"><span class=\"hljs-comment\"># Python program for implementation of Ford Fulkerson algorithm<\/span> <span class=\"hljs-keyword\">from<\/span> collections <span class=\"hljs-keyword\">import<\/span> defaultdict <span class=\"hljs-comment\">#This class represents a directed graph using adjacency matrix representation<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">Graph<\/span>:<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">__init__<\/span><span class=\"hljs-params\">(self,graph)<\/span>:<\/span> self.graph = graph <span class=\"hljs-comment\"># residual graph<\/span> self. ROW = len(graph) <span class=\"hljs-comment\">#self.COL = len(gr[0])<\/span> <span class=\"hljs-string\">'''Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path '''<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">BFS<\/span><span class=\"hljs-params\">(self,s, t, parent)<\/span>:<\/span> <span class=\"hljs-comment\"># Mark all the vertices as not visited<\/span> visited =[<span class=\"hljs-keyword\">False<\/span>]*(self.ROW) <span class=\"hljs-comment\"># Create a queue for BFS<\/span> queue=[] <span class=\"hljs-comment\"># Mark the source node as visited and enqueue it<\/span> queue.append(s) visited[s] = <span class=\"hljs-keyword\">True<\/span> <span class=\"hljs-comment\"># Standard BFS Loop<\/span> <span class=\"hljs-keyword\">while<\/span> queue: <span class=\"hljs-comment\">#Dequeue a vertex from queue and print it<\/span> u = queue.pop(<span class=\"hljs-number\">0<\/span>) <span class=\"hljs-comment\"># Get all adjacent vertices of the dequeued vertex u<\/span> <span class=\"hljs-comment\"># If a adjacent has not been visited, then mark it<\/span> <span class=\"hljs-comment\"># visited and enqueue it<\/span> <span class=\"hljs-keyword\">for<\/span> ind, val <span class=\"hljs-keyword\">in<\/span> enumerate(self.graph[u]): <span class=\"hljs-keyword\">if<\/span> visited[ind] == <span class=\"hljs-keyword\">False<\/span> <span class=\"hljs-keyword\">and<\/span> val &gt; <span class=\"hljs-number\">0<\/span> : queue.append(ind) visited[ind] = <span class=\"hljs-keyword\">True<\/span> parent[ind] = u <span class=\"hljs-comment\"># If we reached sink in BFS starting from source, then return<\/span> <span class=\"hljs-comment\"># true, else false<\/span> <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">True<\/span> <span class=\"hljs-keyword\">if<\/span> visited[t] <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">False<\/span> <span class=\"hljs-comment\"># Returns tne maximum flow from s to t in the given graph<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">FordFulkerson<\/span><span class=\"hljs-params\">(self, source, sink)<\/span>:<\/span> <span class=\"hljs-comment\"># This array is filled by BFS and to store path<\/span> parent = [-<span class=\"hljs-number\">1<\/span>]*(self.ROW) max_flow = <span class=\"hljs-number\">0<\/span> <span class=\"hljs-comment\"># There is no flow initially<\/span> <span class=\"hljs-comment\"># Augment the flow while there is path from source to sink<\/span> <span class=\"hljs-keyword\">while<\/span> self.BFS(source, sink, parent) : <span class=\"hljs-comment\"># Find minimum residual capacity of the edges along the<\/span> <span class=\"hljs-comment\"># path filled by BFS. Or we can say find the maximum flow<\/span> <span class=\"hljs-comment\"># through the path found.<\/span> path_flow = float(<span class=\"hljs-string\">\"Inf\"<\/span>) s = sink <span class=\"hljs-keyword\">while<\/span>(s != source): path_flow = min (path_flow, self.graph[parent[s]][s]) s = parent[s] <span class=\"hljs-comment\"># Add path flow to overall flow<\/span> max_flow += path_flow <span class=\"hljs-comment\"># update residual capacities of the edges and reverse edges<\/span> <span class=\"hljs-comment\"># along the path<\/span> v = sink <span class=\"hljs-keyword\">while<\/span>(v != source): u = parent[v] self.graph[u][v] -= path_flow self.graph[v][u] += path_flow v = parent[v] <span class=\"hljs-keyword\">return<\/span> max_flow <span class=\"hljs-comment\"># Create a graph given in the above diagram<\/span> graph = [[<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">16<\/span>, <span class=\"hljs-number\">13<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>], [<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">10<\/span>, <span class=\"hljs-number\">12<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>], [<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">4<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">14<\/span>, <span class=\"hljs-number\">0<\/span>], [<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">9<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">20<\/span>], [<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">7<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">4<\/span>], [<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">0<\/span>]] g = Graph(graph) source = <span class=\"hljs-number\">0<\/span>; sink = <span class=\"hljs-number\">5<\/span> <span class=\"hljs-keyword\">print<\/span> (<span class=\"hljs-string\">\"The maximum possible flow is %d \"<\/span> % g.FordFulkerson(source, sink))<\/code><\/pre>\n<p>\u6b64\u4ee3\u7801\u4e5f\u662fEdmonds-Karp\u7b97\u6cd5\uff0c\u4f46\u4e0e\u6211\u5b9e\u73b0\u7684\u6709\u6240\u4e0d\u540c\uff0c\u4e0d\u540c\u5728\u4e8e\uff0cBFS\u51fd\u6570\u5728\u6b64\u4ee3\u7801\u91cc\u9762\uff0c\u53ea\u662f\u7528\u6765\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\uff0c\u4f46\u6700\u5927\u6d41\u7684\u8ba1\u7b97\u8fd8\u5f97\u5728\u4e3b\u51fd\u6570\u91cc\uff0c\u901a\u8fc7parent\u8fd9\u4e2alist\u6765\u56de\u6eaf\u627e\u5230\u8def\u5f84\u4e0a\u7684\u6700\u5c0f\u6d41\u7684\u503c\u3002\u800c\u672c\u6587\u5b9e\u73b0\u7684Edmonds-Karp\u7b97\u6cd5\uff0c\u5728BFS\u51fd\u6570\u4e2d\uff0c\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u7684\u540c\u65f6\uff0c\u4e5f\u8ba1\u7b97\u4e86\u8def\u5f84\u7684\u6d41\u7684\u5927\u5c0f\u3002\u6240\u4ee5\u672c\u6587\u5b9e\u73b0\u7684Edmonds-Karp\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u80af\u5b9a\u6bd4\u53cb\u60c5\u94fe\u63a5\u7684Edmonds-Karp\u7b97\u6cd5\u8981\u5c0f\u3002 <br \/> \u53cb\u60c5\u94fe\u63a5\u91cc\u9762\u4e5f\u8bf4\u4e86\uff0c\u5b83\u7684Edmonds-Karp\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-55-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-234\" style=\"width: 4.326em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 3.596em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.148em, 1003.49em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-235\"><span class=\"mi\" id=\"MathJax-Span-236\" style=\"font-family: MathJax_Math-italic;\">O<\/span><span class=\"mo\" id=\"MathJax-Span-237\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-238\" style=\"font-family: MathJax_Math-italic;\">E<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.003em;\"><\/span><\/span><span class=\"msubsup\" id=\"MathJax-Span-239\"><span style=\"display: inline-block; position: relative; width: 1.305em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.18em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-240\" style=\"font-family: MathJax_Math-italic;\">V<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.211em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -4.372em; left: 0.888em;\"><span class=\"mn\" id=\"MathJax-Span-241\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">3<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><span class=\"mo\" id=\"MathJax-Span-242\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.441em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> O ( E V 3 ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-55\">O(EV^3)<\/script>\u3002\u5206\u6790\u4e00\u4e0b\u672c\u6587\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0cBFS\u51fd\u6570\u7684while\u5faa\u73af\u6700\u591aV\u6b21\u6570\uff0c\u4e3b\u51fd\u6570maxflow\u91cc\u9762\u6709\u4e24\u5c42while\u5faa\u73af\uff0c\u7b2c\u4e00\u5c42\u8ddf\u6bcf\u6b21\u7684\u589e\u5e7f\u8def\u5f84\u7684\u9009\u62e9\u6709\u5173\uff0c\u6700\u5dee\u7684\u60c5\u51b5\u6bcf\u6b21\u53ea\u90091\u7684\u91cf\uff0c\u5047\u8bbe\u6700\u5927\u6d41\u662ff\uff0c\u6240\u4ee5\u5916\u5c42\u662ff\u3002\u5185\u5c42\u5faa\u73af\u4e5f\u662f\u6700\u591aV\u6b21\u6570\u3002\u6240\u4ee5\u672c\u6587\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<span class=\"MathJax_Preview\" style=\"color: inherit; display: none;\"><\/span><span class=\"MathJax\" id=\"MathJax-Element-56-Frame\" tabindex=\"0\" style=\"position: relative;\"> <span class=\"math\" id=\"MathJax-Span-243\" style=\"width: 4.065em; display: inline-block;\"><span style=\"display: inline-block; position: relative; width: 3.388em; height: 0px; font-size: 120%;\"><span style=\"position: absolute; clip: rect(1.148em, 1003.28em, 2.555em, -999.997em); top: -2.133em; left: 0em;\"><span class=\"mrow\" id=\"MathJax-Span-244\"><span class=\"mi\" id=\"MathJax-Span-245\" style=\"font-family: MathJax_Math-italic;\">O<\/span><span class=\"mo\" id=\"MathJax-Span-246\" style=\"font-family: MathJax_Main;\">(<\/span><span class=\"mi\" id=\"MathJax-Span-247\" style=\"font-family: MathJax_Math-italic;\">f<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.055em;\"><\/span><\/span><span class=\"msubsup\" id=\"MathJax-Span-248\"><span style=\"display: inline-block; position: relative; width: 1.305em; height: 0px;\"><span style=\"position: absolute; clip: rect(3.18em, 1000.78em, 4.169em, -999.997em); top: -4.008em; left: 0em;\"><span class=\"mi\" id=\"MathJax-Span-249\" style=\"font-family: MathJax_Math-italic;\">V<span style=\"display: inline-block; overflow: hidden; height: 1px; width: 0.211em;\"><\/span><\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><span style=\"position: absolute; top: -4.372em; left: 0.888em;\"><span class=\"mn\" id=\"MathJax-Span-250\" style=\"font-size: 70.7%; font-family: MathJax_Main;\">2<\/span><span style=\"display: inline-block; width: 0px; height: 4.013em;\"><\/span><\/span><\/span><\/span><span class=\"mo\" id=\"MathJax-Span-251\" style=\"font-family: MathJax_Main;\">)<\/span><\/span><span style=\"display: inline-block; width: 0px; height: 2.138em;\"><\/span><\/span><\/span><span style=\"display: inline-block; overflow: hidden; vertical-align: -0.372em; border-left: 0px solid; width: 0px; height: 1.441em;\"><\/span><\/span> <span class=\"MJX_Assistive_MathML\"> O ( f V 2 ) <\/span><\/span><script type=\"math\/tex\" id=\"MathJax-Element-56\">O(fV^2)<\/script>.<\/p>\n<h2 id=\"\u4f7f\u7528dfs\u7684ford-fulkerson\u7b97\u6cd5\">\u4f7f\u7528DFS\u7684Ford-Fulkerson\u7b97\u6cd5<\/h2>\n<p>\u65e2\u7136\u6709\u4e86\u7528BFS\u7684Ford-Fulkerson\u7b97\u6cd5\uff08\u5373Edmonds-Karp\u7b97\u6cd5\uff09\uff0c\u90a3\u6211\u4eec\u518d\u8bbe\u8ba1\u4e00\u4e2a\u7528DFS\u7684Ford-Fulkerson\u7b97\u6cd5\u3002<\/p>\n<h3 id=\"\u9012\u5f52\u8bbe\u8ba1\u9519\u8bef\u793a\u8303\">\u9012\u5f52\u8bbe\u8ba1\u9519\u8bef\u793a\u8303<\/h3>\n<pre class=\"prettyprint\"><code class=\"language-python hljs \"><span class=\"hljs-keyword\">from<\/span> queue <span class=\"hljs-keyword\">import<\/span> Queue <span class=\"hljs-comment\">#n #\u8fb9\u7684\u4e2a\u6570<\/span> m = <span class=\"hljs-number\">6<\/span><span class=\"hljs-comment\">#\u70b9\u7684\u4e2a\u6570<\/span> residual = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u6b8b\u4f59\u56fe\u7684\u5269\u4f59\u6d41\u91cf<\/span> maxflowgraph = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\u56fe\uff0c\u521d\u59cb\u90fd\u4e3a0<\/span> flow = [<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u524d\u8fdb\u8fc7\u7a0b\u8bb0\u5f55\u7684\u6700\u5c0f\u6d41\u91cf<\/span> pre = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u6bcf\u4e2a\u8282\u70b9\u7684\u524d\u9a71\uff0c\u4e5f\u8bb0\u5f55\u8be5\u8282\u70b9\u662f\u5426\u88ab\u8def\u5f84\u8bb0\u5f55<\/span> q = Queue() <span class=\"hljs-comment\">#\u961f\u5217\uff0c\u7528\u4e8eBFS\u5730\u5bfb\u627e\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-comment\">#\u8bbe\u7f6e\u521d\u59cb\u56fe\u7684\u6d41\u91cf\u8d70\u5411<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">1<\/span>]=<span class=\"hljs-number\">3<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">1<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">3<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">4<\/span> residual[<span class=\"hljs-number\">2<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">3<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">3<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">DFS<\/span><span class=\"hljs-params\">(source,progress,sink)<\/span>:<\/span> print(progress,sink) print(flow[progress]) print() <span class=\"hljs-comment\">#source\u5728\u6709\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u4f1a\u4e00\u76f4\u524d\u8fdb\u5230sink<\/span> <span class=\"hljs-keyword\">if<\/span>(progress == sink): <span class=\"hljs-keyword\">return<\/span> flow[sink] <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i==progress) | (i==source) ): <span class=\"hljs-keyword\">continue<\/span> <span class=\"hljs-keyword\">if<\/span>( (residual[progress][i]&gt;<span class=\"hljs-number\">0<\/span>) &amp; (pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>)) ): pre[i] = progress flow[i] = min(flow[progress],residual[progress][i]) <span class=\"hljs-keyword\">return<\/span> DFS(source,i,sink) <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">maxflow<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> sumflow = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\uff0c\u4e00\u76f4\u7d2f\u52a0<\/span> augmentflow = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u5f53\u524d\u5bfb\u627e\u5230\u7684\u589e\u5e7f\u8def\u5f84\u7684\u6700\u5c0f\u901a\u8fc7\u6d41\u91cf<\/span> flow[source] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">True<\/span>): <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): pre[i] = float(<span class=\"hljs-string\">'inf'<\/span>) print(<span class=\"hljs-string\">'\u5bfb\u627e\u589e\u5e7f\u8def\u5f84'<\/span>) augmentflow = DFS(source,source,sink) <span class=\"hljs-comment\">#augmentflow = dfs(source,sink)<\/span> print(<span class=\"hljs-string\">'\u524d\u9a71\u6570\u7ec4\u4e3a'<\/span>,pre) print(<span class=\"hljs-string\">'\u6700\u5927\u6d41\u4e3a'<\/span>,augmentflow) <span class=\"hljs-keyword\">if<\/span>(augmentflow == -<span class=\"hljs-number\">1<\/span>): <span class=\"hljs-keyword\">break<\/span><span class=\"hljs-comment\">#\u8fd4\u56de-1\u8bf4\u660e\u5df2\u6ca1\u6709\u589e\u5e7f\u8def\u5f84<\/span> k = sink <span class=\"hljs-keyword\">while<\/span>(k!=source):<span class=\"hljs-comment\">#k\u56de\u6eaf\u5230\u8d77\u70b9\uff0c\u505c\u6b62<\/span> prev = pre[k]<span class=\"hljs-comment\">#\u8d70\u7684\u65b9\u5411\u662f\u4eceprev\u5230k<\/span> maxflowgraph[prev][k] += augmentflow residual[prev][k] -= augmentflow<span class=\"hljs-comment\">#\u524d\u8fdb\u65b9\u5411\u6d88\u8017\u6389\u4e86<\/span> residual[k][prev] += augmentflow<span class=\"hljs-comment\">#\u53cd\u5411\u8fb9<\/span> k = prev sumflow += augmentflow <span class=\"hljs-keyword\">return<\/span> sumflow result = maxflow(<span class=\"hljs-number\">0<\/span>,m-<span class=\"hljs-number\">1<\/span>) print(result) print(maxflowgraph) <\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726133743617\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c14\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c14\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u622a\u53d6\u4e86\u90e8\u5206\u8fd0\u884c\u7ed3\u679c\u5982\u4e0a\uff0c\u62a5\u5f02\u5e38\u4e86\u7a0b\u5e8f\u7ec8\u6b62\uff1a\u5728\u7b2c\u4e09\u6b21\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u7531\u4e8e\u7a0b\u5e8f\u8d70\u4e86\u4e00\u6761\u9519\u8bef\u7684\u8def\u5f84\uff0c\u5bfc\u81f4\u57283,5\u7684\u65f6\u5019\uff0c\u5373progress\u4e3a3\u7684\u65f6\u5019\uff0c\u5df2\u7ecf\u6ca1\u6709\u8def\u5f84\u53ef\u4ee5\u8d70\u4e86\u3002\u4f46\u7531\u4e8eDFS\u9012\u5f52\u51fd\u6570\u662f\u8fd9\u4e48\u8bbe\u8ba1\u7684\uff1a\u7ec8\u70b9\u5c31<code>return flow[sink]<\/code>\u4e2d\u95f4\u8fc7\u7a0b\u5c31\u662f<code>return DFS(source,i,sink)<\/code>\u3002\u8fd9\u5c31\u5bfc\u81f4\u9012\u5f52\u51fd\u6570\u65e0\u6cd5\u56de\u6eaf\uff0c\u8def\u5f84\u5230\u4e86\u6b7b\u8def\u65e0\u6cd5\u539f\u8def\u8fd4\u56de\u4e00\u4e0b\u518d\u8d70\u4e0b\u4e00\u4e2a\u5206\u652f\u3002\u8fd9\u4e5f\u5bfc\u81f4\u4e86\u6700\u5927\u6d41\u4e3a<code>None<\/code>\uff0c\u56e0\u4e3a\u6839\u636e\u6ca1\u6709\u5230\u8fbe\u9012\u5f52\u7ec8\u70b9\uff0c\u4f46\u8fd9\u4e2a\u9012\u5f52\u51fd\u6570\u8fd8\u975e\u5f97\u8fd4\u56de\u4e00\u4e2a\u503c\uff0c\u6240\u4ee5\u53ea\u6709\u8fd4\u56de\u4e00\u4e2a<code>None<\/code>\u3002 <br \/> \u8fd9\u4e5f\u8bf4\u660e\u4e86\uff0cDFS\u51fd\u6570\u7684\u9012\u5f52\u8bbe\u8ba1\u4e0d\u5e94\u8be5\u8fd9\u4e48\u8bbe\u8ba1\uff0c\u8d77\u7801\u4e0d\u5e94\u8be5\u6709\u8fd9\u79cd\u8fd4\u56de\u81ea\u8eab\u7684\u51fd\u6570\u8bed\u53e5<code>return DFS(source,i,sink)<\/code>\u3002<\/p>\n<h3 id=\"\u9012\u5f52\u6b63\u786e\u8bbe\u8ba1\">\u9012\u5f52\u6b63\u786e\u8bbe\u8ba1<\/h3>\n<pre class=\"prettyprint\"><code class=\" hljs python\"><span class=\"hljs-keyword\">from<\/span> queue <span class=\"hljs-keyword\">import<\/span> Queue <span class=\"hljs-comment\">#n #\u8fb9\u7684\u4e2a\u6570<\/span> m = <span class=\"hljs-number\">6<\/span><span class=\"hljs-comment\">#\u70b9\u7684\u4e2a\u6570<\/span> residual = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u6b8b\u4f59\u56fe\u7684\u5269\u4f59\u6d41\u91cf<\/span> maxflowgraph = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\u56fe\uff0c\u521d\u59cb\u90fd\u4e3a0<\/span> flow = [<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u524d\u8fdb\u8fc7\u7a0b\u8bb0\u5f55\u7684\u6700\u5c0f\u6d41\u91cf<\/span> pre = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u6bcf\u4e2a\u8282\u70b9\u7684\u524d\u9a71\uff0c\u4e5f\u8bb0\u5f55\u8be5\u8282\u70b9\u662f\u5426\u88ab\u8def\u5f84\u8bb0\u5f55<\/span> q = Queue() <span class=\"hljs-comment\">#\u961f\u5217\uff0c\u7528\u4e8eBFS\u5730\u5bfb\u627e\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-comment\">#\u8bbe\u7f6e\u521d\u59cb\u56fe\u7684\u6d41\u91cf\u8d70\u5411<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">1<\/span>]=<span class=\"hljs-number\">3<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">1<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">3<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">4<\/span> residual[<span class=\"hljs-number\">2<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">3<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">3<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">dfs<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): pre[i] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">real_dfs<\/span><span class=\"hljs-params\">(source,progress,sink)<\/span>:<\/span> print(progress,sink) <span class=\"hljs-keyword\">if<\/span>(progress == sink): <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i==progress) | (i==source) ): <span class=\"hljs-keyword\">continue<\/span> <span class=\"hljs-keyword\">if<\/span>( (residual[progress][i]&gt;<span class=\"hljs-number\">0<\/span>) &amp; (pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>)) ): pre[i] = progress flow[i] = min(flow[progress],residual[progress][i]) real_dfs(source,i,sink) real_dfs(source,source,sink) <span class=\"hljs-keyword\">if<\/span>(pre[sink] != float(<span class=\"hljs-string\">'inf'<\/span>)): <span class=\"hljs-keyword\">return<\/span> flow[sink] <span class=\"hljs-keyword\">else<\/span>: <span class=\"hljs-keyword\">return<\/span> -<span class=\"hljs-number\">1<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">maxflow<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> sumflow = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\uff0c\u4e00\u76f4\u7d2f\u52a0<\/span> augmentflow = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u5f53\u524d\u5bfb\u627e\u5230\u7684\u589e\u5e7f\u8def\u5f84\u7684\u6700\u5c0f\u901a\u8fc7\u6d41\u91cf<\/span> flow[source] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">True<\/span>): print(<span class=\"hljs-string\">'\u8c03\u7528\u589e\u5e7f\u8def\u5f84'<\/span>) augmentflow = dfs(source,sink) print(<span class=\"hljs-string\">'\u524d\u9a71\u6570\u7ec4\u4e3a'<\/span>,pre) print(<span class=\"hljs-string\">'\u6700\u5927\u6d41\u4e3a'<\/span>,augmentflow) <span class=\"hljs-keyword\">if<\/span>(augmentflow == -<span class=\"hljs-number\">1<\/span>): <span class=\"hljs-keyword\">break<\/span><span class=\"hljs-comment\">#\u8fd4\u56de-1\u8bf4\u660e\u5df2\u6ca1\u6709\u589e\u5e7f\u8def\u5f84<\/span> k = sink <span class=\"hljs-keyword\">while<\/span>(k!=source):<span class=\"hljs-comment\">#k\u56de\u6eaf\u5230\u8d77\u70b9\uff0c\u505c\u6b62<\/span> prev = pre[k]<span class=\"hljs-comment\">#\u8d70\u7684\u65b9\u5411\u662f\u4eceprev\u5230k<\/span> maxflowgraph[prev][k] += augmentflow residual[prev][k] -= augmentflow<span class=\"hljs-comment\">#\u524d\u8fdb\u65b9\u5411\u6d88\u8017\u6389\u4e86<\/span> residual[k][prev] += augmentflow<span class=\"hljs-comment\">#\u53cd\u5411\u8fb9<\/span> k = prev sumflow += augmentflow <span class=\"hljs-keyword\">return<\/span> sumflow result = maxflow(<span class=\"hljs-number\">0<\/span>,m-<span class=\"hljs-number\">1<\/span>) print(result) print(maxflowgraph) <\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726131701254\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c15\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c15\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u8fd0\u884c\u7ed3\u679c\u5982\u4e0a\uff0c\u7ed3\u679c\u6b63\u786e\u3002\u8fd9\u91cc\u7684dfs\u51fd\u6570\u53ea\u662f\u4e00\u4e2a\u58f3\u5b50\uff0c\u5916\u52a0\u6bcf\u6b21\u521d\u59cb\u5316pre\u3002real_dfs\u51fd\u6570\u624d\u662f\u771f\u6b63\u7684\u9012\u5f52\u51fd\u6570\uff0c\u5f53<code>progress == sink<\/code>\u65f6\uff0c\u5230\u8fbe\u4e86\u9012\u5f52\u7ec8\u70b9\uff0c\u56e0\u4e3a\u7a0b\u5e8f\u5df2\u7ecf\u627e\u5230\u4e86\u589e\u5e7f\u8def\u5f84\u3002\u4f46\u89c2\u5bdf\u8fd0\u884c\u7ed3\u679c\u53d1\u73b0\uff0c\u8c03\u7528\u9012\u5f52\u51fd\u6570\u65f6\uff0c\u6bcf\u6b21\u90fd\u4f1a\u8c03\u75286\u6b21\uff08\u5373\u8282\u70b9\u7684\u4e2a\u6570\uff09\uff0c\u800c\u4e14\u770b\u524d\u4e24\u6b21\u9009\u62e9\u589e\u5e7f\u8def\u5f84\uff0c\u660e\u660e\u90fd\u5df2\u7ecf\u5230\u8fbe<code>5 5<\/code>\uff0c\u4f46\u7a0b\u5e8f\u8fd8\u662f\u5411\u4e0b\u6267\u884c\u4e86\u3002 <br \/> \u8fd9\u662f\u56e0\u4e3a\uff0c\u5982\u6b64\u8bbe\u8ba1\u7684\u9012\u5f52\u51fd\u6570\uff0c\u4f1a\u5c06\u6240\u6709\u9012\u5f52\u5206\u652f\u90fd\u6267\u884c\u4e00\u904d\uff0c\u5373\u4f7f\u4f60\u4ee5\u4e3a\u4f60\u5728\u7ec8\u70b9<code>progress == sink<\/code>\u8bbe\u7f6e\u4e86<code>return<\/code>\uff0c\u4f46\u7a0b\u5e8f\u8fd8\u662f\u6267\u884c\u53ef\u6267\u884c\u7684\u9012\u5f52\u5206\u652f\u3002\uff08\u60f3\u8c61\u4e00\u68f5\u9012\u5f52\u6811\uff0c\u4f1a\u6267\u884c\u5230\u6240\u6709\u7684\u53f6\u5b50\u8282\u70b9\uff09\u3002<\/p>\n<h3 id=\"\u9012\u5f52\u6b21\u6570\u4f18\u5316\">\u9012\u5f52\u6b21\u6570\u4f18\u5316<\/h3>\n<p>\u4fee\u6539dfs\u51fd\u6570\u5982\u4e0b\uff1a<\/p>\n<pre class=\"prettyprint\"><code class=\" hljs python\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">dfs<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): pre[i] = float(<span class=\"hljs-string\">'inf'<\/span>) flag = <span class=\"hljs-keyword\">False<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">real_dfs<\/span><span class=\"hljs-params\">(source,progress,sink)<\/span>:<\/span> <span class=\"hljs-keyword\">nonlocal<\/span> flag <span class=\"hljs-keyword\">if<\/span>(flag == <span class=\"hljs-keyword\">True<\/span>): <span class=\"hljs-keyword\">return<\/span><span class=\"hljs-comment\">#\u6b64\u65f6\u7a0b\u5e8f\u5df2\u7ecf\u627e\u5230\u589e\u5e7f\u8def\u5f84\uff0c\u4e4b\u540e\u7684\u9012\u5f52\u5206\u652f\u4e0d\u9700\u8981\u6267\u884c<\/span> print(progress,sink) <span class=\"hljs-keyword\">if<\/span>(progress == sink): flag = <span class=\"hljs-keyword\">True<\/span> <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i==progress) | (i==source) ): <span class=\"hljs-keyword\">continue<\/span> <span class=\"hljs-keyword\">if<\/span>( (residual[progress][i]&gt;<span class=\"hljs-number\">0<\/span>) &amp; (pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>)) ): pre[i] = progress flow[i] = min(flow[progress],residual[progress][i]) real_dfs(source,i,sink) real_dfs(source,source,sink) <span class=\"hljs-keyword\">if<\/span>(pre[sink] != float(<span class=\"hljs-string\">'inf'<\/span>)): <span class=\"hljs-keyword\">return<\/span> flow[sink] <span class=\"hljs-keyword\">else<\/span>: <span class=\"hljs-keyword\">return<\/span> -<span class=\"hljs-number\">1<\/span><\/code><\/pre>\n<p>\u8bbe\u7f6e\u4e00\u4e2a\u5916\u90e8\u53d8\u91cfflag\uff0c\u4e00\u65e6\u8def\u5f84\u5230\u8fbe\u4e86sink\u70b9\uff0c\u4fbf\u7f6e\u53cdflag\u3002\u5e76\u4e14\u5728\u9012\u5f52\u51fd\u6570\u91cc\u5224\u65ad\u8fd9\u4e2aflag\u3002\u8fd0\u884c\u7ed3\u679c\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726135735753\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c16\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c16\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u53ef\u89c1\uff0c\u6bcf\u6b21\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u53ea\u8981\u9012\u5f52\u5230\u8fbe<code>5 5<\/code>\uff0c\u4e4b\u540e\u7684\u9012\u5f52\u5206\u652f\u4fbf\u6bcf\u6b21\u76f4\u63a5<code>return<\/code>\u3002<\/p>\n<h3 id=\"\u6700\u5927\u6d41\u56fe\u7684\u6700\u540e\u62b5\u6d88\">\u6700\u5927\u6d41\u56fe\u7684\u6700\u540e\u62b5\u6d88<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726140018333\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c17\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c17\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u8fd0\u884c\u7ed3\u679c\u7684\u6700\u5927\u6d41\u56fe\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726140143736\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c18\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c18\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u5b83\u4e0e\u6700\u7ec8\u7684\u6700\u5927\u6d41\u56fe\uff0c\u8fd8\u5dee\u5728\uff0c\u6b63\u53cd\u5411\u8fb9\u8fd8\u6ca1\u6709\u4e92\u76f8\u62b5\u6d88\u6389\u3002\u6240\u4ee5\u5728\u6253\u5370\u6700\u5927\u6d41\u56fe\u524d\uff0c\u6dfb\u52a0\u5982\u4e0b\u4ee3\u7801\u5373\u53ef\u3002<\/p>\n<pre class=\"prettyprint\"><code class=\" hljs glsl\"><span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (maxflowgraph[i][j]!=<span class=\"hljs-number\">0<\/span>)&amp;(maxflowgraph[j][i]!=<span class=\"hljs-number\">0<\/span>)): <span class=\"hljs-preprocessor\">#\u5982\u679c\u7a0b\u5e8f\u7ed3\u675f\u540e\uff0c\u6700\u5927\u6d41\u56fe\u8fd8\u6709\u6b63\u53cd\u5411\u8fb9\u6ca1\u6709\u4e92\u76f8\u62b5\u6d88<\/span> temp = <span class=\"hljs-built_in\">min<\/span>(maxflowgraph[i][j],maxflowgraph[j][i]) maxflowgraph[i][j] -= temp maxflowgraph[j][i] -= temp<\/code><\/pre>\n<h2 id=\"dinic\u7b97\u6cd5\">Dinic\u7b97\u6cd5<\/h2>\n<p>geeksforgeeks\u7684\u53cb\u60c5\u94fe\u63a5Dinic\u2019s algorithm for Maximum Flow\u3002\u867d\u7136\u7528\u82f1\u6587\u5199\u7684\uff0c\u4f46\u662f\u7279\u522b\u597d\u61c2\uff0c\u5927\u5bb6\u53ef\u4ee5\u53bb\u770b\u4e00\u4e0b\uff0c\u6211\u5c31\u662f\u770b\u8fd9\u4e2a\u770b\u61c2\u7684\u3002\u603b\u7684\u6765\u8bf4\uff0cDinic\u2019s\u7b97\u6cd5\u662f\u5c06BFS\u548cDFS\u76f8\u7ed3\u5408\u7684\u7b97\u6cd5\u3002<\/p>\n<blockquote>\n<p>In Edmond\u2019s Karp algorithm, we use BFS to find an augmenting path and send flow across this path. In Dinic\u2019s algorithm, we use BFS to check if more flow is possible and to construct level graph. In level graph, we assign levels to all nodes, level of a node is shortest distance (in terms of number of edges) of the node from source. Once level graph is constructed, we send multiple flows using this level graph. This is the reason it works better than Edmond Karp. In Edmond Karp, we send only flow that is send across the path found by BFS.<\/p>\n<\/blockquote>\n<p>Dinic\u2019s\u7b97\u6cd5\u4e0eEdmond-Karp\u7b97\u6cd5\u7684\u533a\u522b\u5728\u4e8e\u3002\u5728Edmond-Karp\u7b97\u6cd5\u4e2d\uff0c\u6211\u4eec\u7528BFS\u627e\u5230\u589e\u5e7f\u8def\u5f84\u5e76\u4e14\u901a\u8fc7\u8be5\u8def\u5f84\u53d1\u9001\u6d41\u3002\u5728Dinic\u2019s\u7b97\u6cd5\u4e2d\uff0c\u6211\u4eec\u7528BFS\u68c0\u6d4b\u662f\u5426\u6709\u66f4\u591a\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84\uff0c\u4e3a\u6b64\u6211\u4eec\u8981\u6784\u9020\u5c42\u6b21\u56fe\u3002\u5728\u5c42\u6b21\u56fe\u4e2d\uff0c\u7ed9\u6bcf\u4e2a\u8282\u70b9\u6807\u8bb0\u4e00\u4e2a\u6570\uff0c\u8fd9\u4e2a\u6570\u662f\u4ece\u6e90\u70b9\u5230\u8be5\u70b9\u7684\u65e0\u6743\u6700\u77ed\u8def\u5f84\uff08shortest distance in terms of number of edges\uff09\u3002\u4e00\u65e6\u5c42\u6b21\u56fe\u6784\u9020\u597d\u4e86\uff0c\u6211\u4eec\u4fbf\u901a\u8fc7\u5c42\u6b21\u56fe\u6765\u53d1\u9001\u591a\u4e2a\u6d41\u3002\u8fd9\u5c31\u662f\u4e3a\u4ec0\u4e48\u6b64\u7b97\u6cd5\u4f18\u4e8eEdmond-Karp\u7b97\u6cd5\u7684\u539f\u56e0\u3002\u56e0\u4e3aEdmond-Karp\u7b97\u6cd5\u53ea\u4f1a\u6bcf\u6b21\u901a\u8fc7BFS\u627e\u5230\u4e00\u6761\u589e\u5e7f\u8def\u5f84\uff0c\u518d\u53d1\u9001\u8def\u5f84\u4e0a\u7684\u8fd9\u6761\u6d41\u3002 <br \/> \u901a\u8fc7\u5c42\u6b21\u56fe\u6765\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\uff0c\u6bcf\u6761\u589e\u5e7f\u8def\u5f84\u4e0a\u7684\u8282\u70b9\u7684\u5c42\u6b21\u4f9d\u6b21\u4e3a0,1,2,3\u2026\u3002\u5982\u679c\u4ece\u5c42\u6b21\u56fe\u4e2d\uff0c\u5df2\u7ecf\u627e\u4e0d\u5230\u8fd9\u6837\u7684\u8def\u5f84\uff0c\u8bf4\u660e\u8be5\u5c42\u6b21\u56fe\u7684\u53ef\u884c\u7684\u589e\u5e7f\u8def\u5f84\u5df2\u7ecf\u627e\u5b8c\u4e86\u3002<\/p>\n<h3 id=\"\u57fa\u672c\u601d\u60f3-1\">\u57fa\u672c\u601d\u60f3<\/h3>\n<p>\u539f\u56fe\u4ee5\u53ca\u6b8b\u4f59\u56fe\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726225517860\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c19\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c19\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> <strong>\u7b2c\u4e00\u6b21\u8fed\u4ee3\uff1a<\/strong> <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/201807262256380\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c20\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c20\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u4f7f\u7528\u65e0\u6743\u6700\u77ed\u8def\u5f84\u7684\u601d\u60f3\uff08\u628a\u6bcf\u6761\u8fb9\u7684\u6743\u503c\u90fd\u770b\u62101\uff09\uff0c\u4e3a\u6bcf\u4e2a\u70b9\u6807\u6ce8\u5c42\u6b21\uff0c\u6bd4\u5982s\u70b9\u7684\u5c42\u6b21\u4e3a0\uff1b12\u70b9\u7684\u5c42\u6b21\u4e3a1\uff1b34\u70b9\u7684\u5c42\u6b21\u4e3a2\uff1bt\u70b9\u7684\u5c42\u6b21\u4e3a3. <br \/> \u7136\u540e\u6211\u4eec\u5728\u5c42\u6b21\u56fe\uff0c\u5bfb\u627e\u5c42\u6b21\u9010\u6e10\u53d8\u5927\uff08\u5c42\u6b21\u4f9d\u6b21\u4e3a0,1,2,3\u2026\uff09\u7684\u589e\u5e7f\u8def\u5f84\uff0c\u4e00\u65e6\u627e\u5230\u4e00\u6761\u8def\u5f84\uff0c\u4fbf\u5bf9\u6b8b\u4f59\u56fe\u4f5c\u76f8\u5e94\u7684\u4fee\u6539\uff0c\u76f4\u5230\u4e0d\u80fd\u627e\u5230\u8fd9\u6837\u7684\u8def\u5f84\u4e3a\u6b62\u3002 <br \/> \u4e00\u5171\u80fd\u627e\u52303\u6761\u8def\u5f84\uff1a <br \/> 4 units of flow on path s \u2013 1 \u2013 3 \u2013 t. <br \/> 6 units of flow on path s \u2013 1 \u2013 4 \u2013 t. <br \/> 4 units of flow on path s \u2013 2 \u2013 4 \u2013 t. <br \/> Total flow = Total flow + 4 + 6 + 4 = 14 <br \/> <strong>\u7b2c\u4e00\u6b21\u8fed\u4ee3\u4e4b\u540e\uff1a<\/strong> <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726230518927\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c21\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c21\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> <strong>\u7b2c\u4e8c\u6b21\u8fed\u4ee3\uff1a<\/strong> <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726230616312\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c22\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c22\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u4e00\u5171\u627e\u5230\u4e00\u6761\u8def\u5f84\uff1a <br \/> 5 units of flow on path s \u2013 2 \u2013 4 \u2013 3 \u2013 t <br \/> Total flow = Total flow + 5 = 19 <br \/> <strong>\u7b2c\u4e8c\u6b21\u8fed\u4ee3\u4e4b\u540e\uff1a<\/strong> <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726230730278\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c23\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c23\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> <strong>\u7b2c\u4e09\u6b21\u8fed\u4ee3\uff1a<\/strong> <br \/> \u8fd9\u65f6\u6211\u4eec\u53d1\u73b0\uff0c\u518d\u4e5f\u627e\u4e0d\u5230\u5c42\u6b21\u9010\u6e10\u53d8\u5927\uff08\u5c42\u6b21\u4f9d\u6b21\u4e3a0,1,2,3\u2026\uff09\u7684\u589e\u5e7f\u8def\u5f84\u4e86\uff0c\u6240\u4ee5\u7b97\u6cd5\u7ec8\u6b62\u3002<\/p>\n<h3 id=\"\u8bbe\u8ba1\u7a0b\u5e8f\">\u8bbe\u8ba1\u7a0b\u5e8f<\/h3>\n<p>\u5927\u6982\u4f1a\u6709\u4e09\u4e2a\u51fd\u6570\uff1a <br \/> <strong>\u7b2c\u4e00\u4e2a\u662f\u5efa\u7acb\u5c42\u6b21\u56fe\u7684\u51fd\u6570\uff0c\u6bcf\u6b21\u4e3a\u6bcf\u4e2a\u8282\u70b9\u6807\u4e0a\u5c42\u6b21\u53f7\u3002\u6b64\u51fd\u6570\u662f\u7528BFS\u7684\u601d\u8def\u6765\u505a\uff0c\u8fc7\u7a0b\u7c7b\u4f3c\u65e0\u6743\u6700\u77ed\u8def\u5f84\u3002<\/strong> <br \/> <strong>\u7b2c\u4e8c\u4e2a\u662f\u6839\u636e\u5c42\u6b21\u56fe\u627e\u5230\u6240\u6709\u7684\u5c42\u6b21\u9010\u6e10\u53d8\u5927\uff08\u5c42\u6b21\u4f9d\u6b21\u4e3a0,1,2,3\u2026\uff09\u7684\u589e\u5e7f\u8def\u5f84\u3002\u6b64\u51fd\u6570\u662f\u5229\u7528DFS\u7684\u601d\u8def\u6765\u505a\uff0c\u6df1\u5ea6\u9012\u5f52\u5230sink\u65f6\uff0c\u8bf4\u660e\u627e\u5230\u4e86\u4e00\u6761\u589e\u5e7f\u8def\u5f84\u3002<\/strong> <br \/> <strong>\u7b2c\u4e09\u4e2a\u662f\u6839\u636e\u589e\u5e7f\u8def\u5f84\uff0c\u5bf9\u6b8b\u4f59\u56fe\u548c\u6700\u5927\u6d41\u56fe\u4f5c\u51fa\u76f8\u5e94\u7684\u4fee\u6539\u3002<\/strong> <br \/> \u5927\u4f53\u601d\u8def\u662f\u8fd9\u6837\uff0c\u4f46\u5b9e\u9645\u7f16\u7a0b\u4e2d\u6709\u6240\u51fa\u5165\uff0c\u4f46\u7406\u89e3\u8fd9\u4e2a\u601d\u8def\uff0c\u662f\u5f88\u91cd\u8981\u7684\u3002 <br \/> \u4ece\u4e0a\u9762\u53ef\u4ee5\u770b\u51fa\u6765\uff0cDinic\u2019s\u7b97\u6cd5\u662f\u5c06BFS\u548cDFS\u76f8\u7ed3\u5408\u7684\u7b97\u6cd5\u3002<\/p>\n<h3 id=\"\u4ee3\u7801\u5b9e\u73b0\">\u4ee3\u7801\u5b9e\u73b0<\/h3>\n<p>\u4f7f\u7528\u7684\u56fe\uff0c\u4ee5\u53ca\u5176\u6700\u5927\u6d41\u56fe\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180726233748220\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c24\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c24\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> \u6309\u7167\u4ee5\u4e0a\u8bbe\u8ba1\u7a0b\u5e8f\u7684\u601d\u8def\uff0c\u7528python3\u5b9e\u73b0\u4e86\u5982\u4e0b\u4ee3\u7801\uff1a<\/p>\n<pre class=\"prettyprint\"><code class=\" hljs python\"><span class=\"hljs-keyword\">from<\/span> queue <span class=\"hljs-keyword\">import<\/span> Queue <span class=\"hljs-comment\">#n #\u8fb9\u7684\u4e2a\u6570<\/span> m = <span class=\"hljs-number\">6<\/span><span class=\"hljs-comment\">#\u70b9\u7684\u4e2a\u6570<\/span> residual = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u6b8b\u4f59\u56fe\u7684\u5269\u4f59\u6d41\u91cf<\/span> maxflowgraph = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\u56fe\uff0c\u521d\u59cb\u90fd\u4e3a0<\/span> flow = [<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u524d\u8fdb\u8fc7\u7a0b\u8bb0\u5f55\u7684\u6700\u5c0f\u6d41\u91cf<\/span> pre = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u6bcf\u4e2a\u8282\u70b9\u7684\u524d\u9a71\uff0c\u4e5f\u8bb0\u5f55\u8be5\u8282\u70b9\u662f\u5426\u88ab\u8def\u5f84\u8bb0\u5f55<\/span> level = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u4ee3\u8868\u5c42\u6b21\u56fe\uff0c\u5c42\u6b21\u4ece0\u5f00\u59cb<\/span> sumflow = <span class=\"hljs-number\">0<\/span> <span class=\"hljs-comment\">#\u8bbe\u7f6e\u521d\u59cb\u56fe\u7684\u6d41\u91cf\u8d70\u5411<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">1<\/span>]=<span class=\"hljs-number\">10<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">10<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">4<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">8<\/span> residual[<span class=\"hljs-number\">2<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">9<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">6<\/span> residual[<span class=\"hljs-number\">3<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">10<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">10<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">build_level<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> <span class=\"hljs-comment\">#\u6839\u636e\u6b8b\u4f59\u56fe\u6765\u6784\u5efa\u5c42\u6b21\u56fe,\u8fc7\u7a0b\u7c7b\u4f3c\u65e0\u6743\u6700\u77ed\u8def\u5f84<\/span> level[source] = <span class=\"hljs-number\">0<\/span><span class=\"hljs-comment\">#\u6e90\u70b9\u7684\u5c42\u6b21\u4e3a0<\/span> level_pre = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u6784\u9020\u5c42\u6b21\u56fe\u7528\u5230\u7684\u524d\u9a71\u8868\uff0c\u7528\u6765\u6807\u8bb0\u8be5\u8282\u70b9\u5df2\u6807\u8bb0\u4e3a\u5c42\u6b21<\/span> q = Queue() <span class=\"hljs-comment\">#\u961f\u5217\uff0c\u7528\u4e8eBFS\u5730\u5bfb\u627e\u589e\u5e7f\u8def\u5f84<\/span> q.put(source) <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">not<\/span> q.empty()): current = q.get() <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i==source) | (i==current) ): <span class=\"hljs-keyword\">continue<\/span><span class=\"hljs-comment\">#\u6e90\u70b9\u548c\u81ea\u8eab\u4e0d\u7528\u5206\u6790<\/span> <span class=\"hljs-keyword\">if<\/span>((residual[current][i]&gt;<span class=\"hljs-number\">0<\/span>)&amp;(level_pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>))): <span class=\"hljs-comment\">#\u53ea\u8981\u80fd\u5f80\u4e0b\u8d70\u4e14\u6ca1\u6709\u88ab\u6807\u8bb0\u8fc7<\/span> level_pre[i] = current <span class=\"hljs-comment\">#\u6807\u8bb0\u524d\u9a71\uff0c\u4e5f\u4ee3\u8868\u5df2\u6784\u9020\u4e86\u5c42\u6b21<\/span> level[i] = level[current]+<span class=\"hljs-number\">1<\/span> <span class=\"hljs-comment\">#\u5c42\u6b21\u9010\u6e10\u52a01<\/span> q.put(i) <span class=\"hljs-comment\">#\u52a0\u5165\u961f\u5217<\/span> print(<span class=\"hljs-string\">'\u5c42\u6b21\u56fe\u4e3a'<\/span>,level) <span class=\"hljs-keyword\">if<\/span>(level_pre[sink]!=float(<span class=\"hljs-string\">'inf'<\/span>)): <span class=\"hljs-comment\">#\u5982\u679c\u6784\u9020\u5c42\u6b21\u56fe\u80fd\u6784\u9020\u5230sink\u70b9\uff0c\u8bf4\u660e\u6709\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">True<\/span> <span class=\"hljs-keyword\">else<\/span>: <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">False<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">get_augment<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> <span class=\"hljs-comment\">#\u6839\u636e\u5c42\u6b21\u56fe\uff0c\u6784\u9020\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84<\/span> temp_augment = [source] <span class=\"hljs-comment\">#\u6bcf\u6761\u589e\u5e7f\u8def\u5f84\u90fd\u662f\u4ece\u6e90\u70b9\u5f00\u59cb\u7684<\/span> count = <span class=\"hljs-number\">1<\/span><span class=\"hljs-comment\">#\u6e90\u70b9\u4e0b\u4e00\u5c42\u7684\u5c42\u6b21\u4e3a1<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">recursion<\/span><span class=\"hljs-params\">(count)<\/span>:<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>(level[i]==count):<span class=\"hljs-comment\">#\u5bfb\u627e\u5c42\u6b21\u4e3acount\u7684\u70b9<\/span> temp_augment.append(i) <span class=\"hljs-keyword\">if<\/span>(i == sink): <span class=\"hljs-comment\">#i\u5230\u4e86sink\uff0c\u8bf4\u660e\u627e\u5230\u4e86\u4e00\u6761\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84<\/span> print(<span class=\"hljs-string\">'\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84'<\/span>,temp_augment) <span class=\"hljs-comment\">#\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84\u662f\u5c42\u6b21\u56fe\u7684\u6392\u5217\u7ec4\u5408\u800c\u6765<\/span> send_flow(temp_augment,source,sink) recursion(count+<span class=\"hljs-number\">1<\/span>)<span class=\"hljs-comment\">#\u5bfb\u627e\u4e0b\u4e00\u5c42\u6b21\u7684\u70b9<\/span> temp_augment.remove(i) <span class=\"hljs-comment\">#\u5220\u9664\u6389i\uff0c\u4e3a\u4e0b\u4e00\u6b21\u9012\u5f52\u4f5c\u51c6\u5907<\/span> recursion(count) print() <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">send_flow<\/span><span class=\"hljs-params\">(augment,source,sink)<\/span>:<\/span> <span class=\"hljs-comment\">#\u6839\u636e\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84\uff0c\u5224\u65ad\u5176\u662f\u5426\u4e3a\u4e00\u6761\u53ef\u884c\u7684\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-keyword\">global<\/span> sumflow flow[sink] = float(<span class=\"hljs-string\">'inf'<\/span>)<span class=\"hljs-comment\">#\u8bbe\u4e3a\u65e0\u7a77\uff0c\u4e14\u4ee5\u8fd9\u4e2a\u4f5c\u4e3a\u627e\u5230\u589e\u5e7f\u8def\u5f84\u7684\u6807\u5fd7<\/span> print(<span class=\"hljs-string\">'\u521d\u59cbflow'<\/span>,flow) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(len(augment)-<span class=\"hljs-number\">1<\/span>): flow[augment[i+<span class=\"hljs-number\">1<\/span>]] = min(flow[augment[i]],residual[augment[i]][augment[i+<span class=\"hljs-number\">1<\/span>]]) print(<span class=\"hljs-string\">'\u884c\u8fdb\u589e\u5e7f\u8def\u5f84\u8fc7\u7a0b\u4e2d\u7684flow'<\/span>,flow) <span class=\"hljs-keyword\">if<\/span>(flow[sink] != <span class=\"hljs-number\">0<\/span>): <span class=\"hljs-comment\">#flow[sink]\u4e0d\u4e3a0\uff0c\u8bf4\u660e\u589e\u5e7f\u8def\u5f84\u6709\u6548<\/span> sumflow += flow[sink] print(<span class=\"hljs-string\">'\u6709\u6548\u7684\u589e\u5e7f\u8def\u5f84'<\/span>,augment,flow) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(len(augment)-<span class=\"hljs-number\">1<\/span>): <span class=\"hljs-comment\">#\u5bf9\u6b8b\u4f59\u56fe\u548c\u6700\u5927\u6d41\u56fe\u7684\u76f8\u5e94\u4fee\u6539<\/span> residual[augment[i]][augment[i+<span class=\"hljs-number\">1<\/span>]] -= flow[sink] residual[augment[i+<span class=\"hljs-number\">1<\/span>]][augment[i]] += flow[sink] maxflowgraph[augment[i]][augment[i+<span class=\"hljs-number\">1<\/span>]] += flow[sink] print() <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">dinic<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> flow[source] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-comment\">#\u6e90\u70b9\u7684flow\u4e3a\u65e0\u7a77\uff0c\u65b9\u4fbf\u4ee5\u540e\u53d6\u8f83\u5c0f\u6570\uff0c\u4e14\u6e90\u70b9\u7684flow\u6c38\u8fdc\u4e3a\u65e0\u7a77<\/span> <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">True<\/span>): temp = build_level(source,sink) <span class=\"hljs-keyword\">if<\/span>(temp <span class=\"hljs-keyword\">is<\/span> <span class=\"hljs-keyword\">False<\/span>): <span class=\"hljs-keyword\">break<\/span> <span class=\"hljs-keyword\">else<\/span>: get_augment(source,sink) dinic(<span class=\"hljs-number\">0<\/span>,m-<span class=\"hljs-number\">1<\/span>) print(sumflow) print(maxflowgraph)<\/code><\/pre>\n<p>\u4ee3\u7801\u7684\u5177\u4f53\u7ec6\u8282\u8bf7\u770b\u6ce8\u91ca\u3002\u8fd0\u884c\u7ed3\u679c\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180727124224664\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c25\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c25\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> <strong>\u4e3b\u51fd\u6570dinic<\/strong>\u4e00\u76f4\u8c03\u7528build_level\u51fd\u6570\uff0c\u6765\u67e5\u770b\u662f\u5426\u80fd\u5728\u5f53\u524d\u6b8b\u4f59\u56fe\u4e0a\u5efa\u7acb\u5c42\u6b21\u56fe\uff0c\u5982\u679c\u4e0d\u80fd\uff0c\u8bf4\u660e\u6700\u5927\u6d41\u5df2\u7ecf\u627e\u5b8c\u4e86\uff0c\u4fbf\u7ed3\u675f\u5faa\u73af\u3002 <br \/> <strong>build_level\u51fd\u6570<\/strong>\uff0c\u6839\u636e\u5f53\u524d\u6b8b\u4f59\u56fe\u5efa\u7acb\u6b8b\u4f59\u56fe\uff0c\u8fc7\u7a0b\u7c7b\u4f3c\u4e8e\u65e0\u6743\u6700\u77ed\u8def\u5f84\uff08BFS\uff09\uff0c\u5229\u7528\u961f\u5217\u548c\u524d\u9a71\u6570\u7ec4level_pre\u6765\u5b9e\u73b0\uff0c\u5982\u679c\u80fd\u5efa\u7acb\u5c42\u6b21\u56fe\uff0c\u8fd4\u56de\u771f\uff0c\u5426\u5219\u8fd4\u56de\u5047\u3002 <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/201807262256380\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c20\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c20\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> <strong>get_augment\u51fd\u6570<\/strong>\uff0c\u6839\u636e\u5f53\u524d\u5c42\u6b21\u56fe\u83b7\u5f97\u4e00\u6761\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84\uff08\u4e3a\u4ec0\u4e48\u662f\u8bf4\u53ef\u80fd\u5462\uff0c\u56e0\u4e3a\u8fd9\u662f\u901a\u8fc7\u5c42\u6b21\u4ece\u4f4e\u5230\u9ad8\u6392\u5217\u7ec4\u5408\u800c\u6765\u7684\uff0c\u6bd4\u5982\u901a\u8fc7\u7b2c\u4e00\u6b21\u5c42\u6b21\u56fe\u4f1a\u53d1\u73b0\u56db\u6761\u53ef\u80fd\u7684\u589e\u5e7f\u8def\u5f84\uff1a[0, 1, 3, 5]\uff0c[0, 1, 4, 5]\uff0c[0, 2, 3, 5]\uff0c [0, 2, 4, 5]\u3002\u770b\u4e0a\u56fe\u53ef\u4ee5\u53d1\u73b0\u53ea\u67094\u6761\u53ef\u80fd\u7684\u8def\u5f84\u3002\u4f46\u5b9e\u9645\u4e0a\u6709\u6548\u7684\u53ea\u6709\uff0c[0, 1, 3, 5]\uff0c[0, 1, 4, 5]\uff0c [0, 2, 4, 5]\uff09\u3002\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u7684\u65b9\u6cd5\u662f\u901a\u8fc7DFS\u5373\u6df1\u5ea6\u904d\u5386\uff0c\u4e00\u65e6\u53d1\u73b0\u4e00\u6761\u589e\u5e7f\u8def\u5f84\uff0c\u4fbf\u5c06\u8def\u5f84\u4f20\u7ed9send_flow\u51fd\u6570\u3002 <br \/> <strong>send_flow\u51fd\u6570<\/strong>\uff0c\u6839\u636e\u4f20\u6765\u7684\u589e\u5e7f\u8def\u5f84\u548c\u5f53\u524d\u7684\u6b8b\u4f59\u56fe\uff0c\u5982\u679c\u901a\u8fc7\u4f20\u6765\u7684\u8def\u5f84\u80fd\u6d41\u8fc7\u4e0d\u4e3a0\u7684\u6d41\uff08\u5982\u679c\u8def\u5f84\u4e0d\u6709\u6548\uff0c\u90a3\u4e48\u8d70\u5b8c\u8def\u5f84\uff0c\u6d41\u7684\u91cf\u4e3a0\uff09\uff0c\u90a3\u4e48\u5224\u65ad\u6b64\u589e\u5e7f\u8def\u5f84\u6709\u6548\uff0c\u518d\u5bf9\u6b8b\u4f59\u56fe\u4ee5\u53ca\u6700\u5927\u6d41\u56fe\u4f5c\u76f8\u5e94\u7684\u4fee\u6539<\/p>\n<p>\u6b64\u4ee3\u7801\u5b9e\u73b0\uff0c\u7ed3\u6784\u5c42\u6b21\u6e05\u6670\uff0c\u65b9\u4fbf\u7f16\u7a0b\u5b9e\u73b0\u3002<\/p>\n<h3 id=\"\u53e6\u4e00\u79cd\u4ee3\u7801\u5b9e\u73b0\">\u53e6\u4e00\u79cd\u4ee3\u7801\u5b9e\u73b0<\/h3>\n<p>\u7531\u4e8e\u672c\u4eba\u7684\u5947\u601d\u5999\u60f3\uff0c\u6211\u5c31\u60f3\uff0c\u80fd\u4e0d\u80fd\u7f16\u5199\u8fd9\u4e48\u591a\u51fd\u6570\u3002\u6700\u597d\u53ea\u7528\u4e00\u4e2a\u51fd\u6570\uff1a\u9996\u5148\u53ef\u4ee5\u4e0d\u9700\u8981\u5c42\u6b21\u56fe\uff0c\u53ea\u9700\u8981\u6309\u7167\u5c42\u6b21\u6765\u524d\u8fdb\u9009\u62e9\u589e\u5e7f\u8def\u5f84\uff1b\u9009\u62e9\u589e\u5e7f\u8def\u5f84\u8fd8\u662f\u6309\u7167DFS\u7684\u601d\u60f3\uff08\u80af\u5b9a\u5f97\u7528\u5230\u9012\u5f52\uff09\uff1b\u6bcf\u5f53\u627e\u5230\u4e00\u6761\u53ef\u884c\u7684\u589e\u5e7f\u8def\u5f84\u4fbf\u5bf9\u6b8b\u4f59\u56fe\u4f5c\u4fee\u6539\u3002 <br \/> \u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre class=\"prettyprint\"><code class=\" hljs python\"><span class=\"hljs-comment\">#n #\u8fb9\u7684\u4e2a\u6570<\/span> m = <span class=\"hljs-number\">6<\/span><span class=\"hljs-comment\">#\u70b9\u7684\u4e2a\u6570<\/span> residual = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u6b8b\u4f59\u56fe\u7684\u5269\u4f59\u6d41\u91cf<\/span> maxflowgraph = [[<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-keyword\">for<\/span> j <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41\u56fe\uff0c\u521d\u59cb\u90fd\u4e3a0<\/span> flow = [<span class=\"hljs-number\">0<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u524d\u8fdb\u8fc7\u7a0b\u8bb0\u5f55\u7684\u6700\u5c0f\u6d41\u91cf<\/span> pre = [float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m)] <span class=\"hljs-comment\">#\u8bb0\u5f55\u589e\u5e7f\u8def\u5f84\u6bcf\u4e2a\u8282\u70b9\u7684\u524d\u9a71\uff0c\u4e5f\u8bb0\u5f55\u8be5\u8282\u70b9\u662f\u5426\u88ab\u8def\u5f84\u8bb0\u5f55<\/span> sumflow = <span class=\"hljs-number\">0<\/span> <span class=\"hljs-comment\">#\u8bb0\u5f55\u6700\u5927\u6d41<\/span> <span class=\"hljs-comment\">#\u8bbe\u7f6e\u521d\u59cb\u56fe\u7684\u6d41\u91cf\u8d70\u5411<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">1<\/span>]=<span class=\"hljs-number\">10<\/span> residual[<span class=\"hljs-number\">0<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">10<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">2<\/span>]=<span class=\"hljs-number\">2<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">4<\/span> residual[<span class=\"hljs-number\">1<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">8<\/span> residual[<span class=\"hljs-number\">2<\/span>][<span class=\"hljs-number\">4<\/span>]=<span class=\"hljs-number\">9<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">3<\/span>]=<span class=\"hljs-number\">6<\/span> residual[<span class=\"hljs-number\">3<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">10<\/span> residual[<span class=\"hljs-number\">4<\/span>][<span class=\"hljs-number\">5<\/span>]=<span class=\"hljs-number\">10<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">label_next_level<\/span><span class=\"hljs-params\">(source,progress)<\/span>:<\/span> <span class=\"hljs-comment\">#\u6807\u8bb0progress\u8282\u70b9\u7684\u4e0b\u4e00\u5c42\u6b21\u7684\u8282\u70b9\u5bf9\u5e94\u7684pre<\/span> <span class=\"hljs-comment\">#\u5e76\u4e14label\u6570\u7ec4\u4fdd\u5b58\u6807\u8bb0\u7684\u8282\u70b9<\/span> label = [] <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i==progress) | (i==source) ): <span class=\"hljs-keyword\">continue<\/span> <span class=\"hljs-keyword\">if<\/span>( (residual[progress][i]&gt;<span class=\"hljs-number\">0<\/span>) &amp; (pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>)) ): label.append(i) pre[i] = progress <span class=\"hljs-keyword\">return<\/span> label <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">nonlabel_next_level<\/span><span class=\"hljs-params\">(label)<\/span>:<\/span> <span class=\"hljs-comment\">#\u4e3a\u4e0b\u4e00\u6b21\u9012\u5f52\u5206\u652f\u4f5c\u51c6\u5907\u65f6\uff0c\u8c03\u7528\u6b64\u51fd\u6570<\/span> <span class=\"hljs-comment\">#\u5c06label_next_level\u51fd\u6570\u6807\u8bb0\u8fc7\u7684\u8282\u70b9<\/span> <span class=\"hljs-comment\">#\u518d\u6807\u8bb0\u56de\u65e0\u7a77<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> label: pre[i] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">solve<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> print(<span class=\"hljs-string\">'\u65b0\u7684\u4e00\u6b21\u8c03\u7528'<\/span>) <span class=\"hljs-comment\">#\u867d\u7136\u611f\u89c9\u9700\u8981\u4fdd\u5b58\u5c42\u6b21\u56fe\u4fe1\u606f\uff0c\u4f46\u5b9e\u9645\u53ea\u8981\u65e0\u6743\u6700\u77ed\u8def\u5f84\u8fdb\u884c\u5c31\u884c<\/span> <span class=\"hljs-comment\">#\u6240\u4ee5\u6b64\u7a0b\u5e8f\u6ca1\u6709\u6570\u636e\u7ed3\u6784\u4fdd\u5b58\u5c42\u6b21\u56fe\uff0c\u4f46\u4e0b\u9762\u7684bfs\u51fd\u6570\u662f\u6309\u7167\u5c42\u6b21\u56fe<\/span> <span class=\"hljs-comment\">#\u5c42\u6b21\u5927\u5c0f\u987a\u5e8f\u8fdb\u884c\u9012\u5f52\u7684<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): pre[i] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-comment\">#\u521d\u59cb\u5316pre\u6570\u7ec4<\/span> level_path = [source] <span class=\"hljs-comment\">#\u6b64list\u4fdd\u5b58\u9012\u5f52\u4e2d\u627e\u5230\u7684\u589e\u5e7f\u8def\u5f84\uff0c\u5fc5\u6709source<\/span> flag = <span class=\"hljs-keyword\">False<\/span> <span class=\"hljs-comment\">#\u6b64\u6807\u5fd7\u4f4d\u5c31\u6765\u8868\u793a\u6b64\u6b21\u8c03\u7528solve\u51fd\u6570\u662f\u5426\u6709\u627e\u5230\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">bfs<\/span><span class=\"hljs-params\">(progress,sink)<\/span>:<\/span> label = []<span class=\"hljs-comment\">#\u4fdd\u5b58\u5728pre\u91cc\u6807\u8bb0\u8fc7\u7684\u8282\u70b9<\/span> <span class=\"hljs-keyword\">nonlocal<\/span> level_path,flag <span class=\"hljs-keyword\">global<\/span> sumflow <span class=\"hljs-keyword\">if<\/span>(progress == sink):<span class=\"hljs-comment\">#\u9012\u5f52\u7ec8\u70b9\uff0c\u4f46\u8fd9\u4e48\u8bf4\u4e0d\u51c6\u786e\uff0c\u56e0\u4e3a\u4e4b\u540e\u9012\u5f52\u8fd8\u5728\u6267\u884c<\/span> <span class=\"hljs-comment\">#\u56e0\u4e3a\u53ef\u80fd\u8fd8\u6709\u589e\u5e7f\u8def\u5f84\uff0c\u6240\u4ee5\u5f97\u6267\u884c\u5b8c\u6240\u6709\u9012\u5f52\u5206\u652f<\/span> <span class=\"hljs-comment\">#\u6bcf\u5f53\u5230\u4e86\u8fd9\u4e2a\u5206\u652f\uff0c\u5c31\u8bf4\u660e\u627e\u5230\u4e86\u4e00\u6761\u589e\u5e7f\u8def\u5f84<\/span> flag = <span class=\"hljs-keyword\">True<\/span> <span class=\"hljs-comment\">#\u7f6e\u53cdflag<\/span> sumflow += flow[sink] <span class=\"hljs-comment\">#\u6700\u5927\u6d41\u7684\u91cf<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(len(level_path)-<span class=\"hljs-number\">1<\/span>): <span class=\"hljs-comment\">#\u5bf9\u6700\u5927\u6d41\u56fe\u548c\u6b8b\u4f59\u56fe\u505a\u76f8\u5e94\u7684\u64cd\u4f5c<\/span> residual[level_path[i]][level_path[i+<span class=\"hljs-number\">1<\/span>]] -= flow[sink] residual[level_path[i+<span class=\"hljs-number\">1<\/span>]][level_path[i]] += flow[sink] maxflowgraph[level_path[i]][level_path[i+<span class=\"hljs-number\">1<\/span>]] += flow[sink] <span class=\"hljs-comment\">#\u6839\u636e\u5c42\u6b21\u8def\u5f84\uff0c\u66f4\u65b0flow\uff0c\u4e3a\u4e0b\u4e00\u6b21\u4f5c\u51c6\u5907<\/span> <span class=\"hljs-comment\">#\u8fd9\u91cc\u662f\u63d0\u524d\u8ba1\u7b97\u597dflow\uff0c\u672c\u6765flow\u662f\u6bcf\u6b21\u627e\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u4ece\u5934\u5f00\u59cb\u7b97\uff0c\u800c\u4e14\u4e0d\u7528\u63d0\u524d<\/span> <span class=\"hljs-comment\">#\u4f46\u7531\u4e8e\u7b2c\u4e8c\u6b21\u627e\u589e\u5e7f\u8def\u5f84\u65f6\uff0c\u662f\u4ece\u9012\u5f52\u7684\u67d0\u6b21\u5206\u652f\u627e\u5230\u7684\uff0c\u4f46\u5206\u652f\u7684\u8fd9\u4e2a\u8282\u70b9\u7684flow<\/span> <span class=\"hljs-comment\">#\u8fd8\u6ca1\u6709\u6309\u7167\u4ece\u6e90\u70b9\u66f4\u65b0flow\u90a3\u4e48\u66f4\u65b0\u597d<\/span> <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(len(level_path)-<span class=\"hljs-number\">1<\/span>): <span class=\"hljs-keyword\">if<\/span>(residual[level_path[i]][level_path[i+<span class=\"hljs-number\">1<\/span>]] &gt; <span class=\"hljs-number\">0<\/span>): flow[level_path[i+<span class=\"hljs-number\">1<\/span>]] = min(residual[level_path[i]][level_path[i+<span class=\"hljs-number\">1<\/span>]],flow[level_path[i]]) <span class=\"hljs-keyword\">else<\/span>: <span class=\"hljs-comment\">#\u5982\u679c\u5c0f\u4e8e\u7b49\u4e8e0\u4e86\uff0c\u8bf4\u660e\u7b2c\u4e8c\u6b21\u589e\u5e7f\u8def\u5f84\u4e5f\u80af\u5b9a\u4e0d\u4f1a\u4ece\u8fd9\u4e2a\u5206\u652f\u5206\u652f\u4e86<\/span> <span class=\"hljs-keyword\">break<\/span> print(level_path) print(flow[sink]) <span class=\"hljs-keyword\">for<\/span> i <span class=\"hljs-keyword\">in<\/span> range(m): <span class=\"hljs-keyword\">if<\/span>( (i==progress) | (i==source) ): <span class=\"hljs-comment\">#\u524d\u8fdb\u8fc7\u7a0b\u4e0d\u80fd\u56de\u5230\u6e90\u70b9source<\/span> <span class=\"hljs-comment\">#\u524d\u8fdb\u8fc7\u7a0b\u4e5f\u4e0d\u80fd\u56de\u5230\u81ea\u8eabprogress<\/span> <span class=\"hljs-keyword\">continue<\/span> <span class=\"hljs-keyword\">if<\/span>( (residual[progress][i]&gt;<span class=\"hljs-number\">0<\/span>) &amp; (pre[i]==float(<span class=\"hljs-string\">'inf'<\/span>)) ): <span class=\"hljs-comment\">#\u4eceprogress\u5230i\u6709\u6b63\u5411\u8fb9\uff0c\u4e14i\u6ca1\u6709\u88ab\u6807\u8bb0\u8fc7<\/span> level_path.append(i) label = label_next_level(source,progress) <span class=\"hljs-comment\">#\u6807\u6ce8progress\u4e0b\u4e00\u5c42\u6b21\u7684\u8282\u70b9<\/span> flow[i] = min(flow[progress],residual[progress][i]) print(progress,i,<span class=\"hljs-string\">'before'<\/span>,pre) bfs(i,sink) level_path.remove(i) nonlabel_next_level(label) print(progress,i,<span class=\"hljs-string\">'after'<\/span>,pre) bfs(source,sink) <span class=\"hljs-keyword\">return<\/span> flag <span class=\"hljs-function\"><span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title\">dinic<\/span><span class=\"hljs-params\">(source,sink)<\/span>:<\/span> flow[source] = float(<span class=\"hljs-string\">'inf'<\/span>) <span class=\"hljs-comment\">#\u6e90\u70b9\u7684flow\u4e3a\u65e0\u7a77\uff0c\u65b9\u4fbf\u4ee5\u540e\u53d6\u8f83\u5c0f\u6570\uff0c\u4e14\u6e90\u70b9\u7684flow\u6c38\u8fdc\u4e3a\u65e0\u7a77<\/span> <span class=\"hljs-keyword\">while<\/span>(<span class=\"hljs-keyword\">True<\/span>): temp = solve(source,sink) <span class=\"hljs-comment\">#solve\u51fd\u6570\u6bcf\u6b21\u8fdb\u884c\u5c42\u6b21\u56fe\u7684\u904d\u5386<\/span> <span class=\"hljs-comment\">#solve\u51fd\u6570\u6bcf\u6b21\u6709\u53ef\u80fd\u6839\u636e\u5c42\u6b21\u56fe\u627e\u51fa\u591a\u4e2a\u589e\u5e7f\u8def\u5f84<\/span> <span class=\"hljs-keyword\">if<\/span>(temp <span class=\"hljs-keyword\">is<\/span> <span class=\"hljs-keyword\">False<\/span>): <span class=\"hljs-keyword\">break<\/span> <span class=\"hljs-keyword\">return<\/span> sumflow result = dinic(<span class=\"hljs-number\">0<\/span>,m-<span class=\"hljs-number\">1<\/span>) print() print(result) print(maxflowgraph)<\/code><\/pre>\n<p>\u4ee3\u7801\u7684\u5177\u4f53\u7ec6\u8282\u8bf7\u770b\u6ce8\u91ca\u3002\u8fd0\u884c\u7ed3\u679c\u5982\u4e0b\uff1a <br \/> <img decoding=\"async\" src=\"https:\/\/img-blog.csdn.net\/20180727122115406\" =\"\" =\"\u8fd9\u91cc\u5199\u56fe\u7247\u63cf\u8ff0\" alt=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5 (https:\/\/mushiming.com\/)  \u7b2c27\u5f20\" title=\"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5  \u7b2c27\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" > <br \/> <strong>\u6b64\u4ee3\u7801\u7684\u7cbe\u534e\u5728\u4e8e\uff0c\u4f7f\u7528\u5c42\u6b21\u56fe\u7684\u601d\u60f3\uff0c\u6bcf\u5f53\u9012\u5f52\u5230\u7b2ci\u5c42\uff0c\u5c31\u628a\u7b2ci\u5c42\u7684\u8282\u70b9\u90fd\u7ed9\u6807\u8bb0\u6210\u5df2\u8d70\u8fc7\uff08\u6807\u8bb0pre\u6570\u7ec4\uff0c\u901a\u8fc7\u8c03\u7528label_next_level\u51fd\u6570\uff09\uff0c\u8fd9\u6837\uff0c\u5728\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\u65f6\uff0c\u80af\u5b9a\u53ea\u80fd\u5bfb\u627e\u5230i+1\u5c42\u7684\u8282\u70b9\uff0c\u8fd9\u6837\u5c31\u4e0d\u9700\u8981\u5c42\u6b21\u56fe\u5c31\u5b9e\u73b0\u4e86\u5c42\u6b21\u56fe\u7684\u529f\u80fd\u3002\u5e76\u4e14\u5f53\u6b64\u5c42\u9012\u5f52\u7ed3\u675f\u524d\uff0c\u5c06label_next_level\u51fd\u6570\u6807\u8bb0\u8fc7\u7684\u8282\u70b9\uff0c\u518d\u6807\u8bb0\u56de\u521d\u59cb\u72b6\u6001\uff08\u901a\u8fc7label\u6570\u7ec4\u8bb0\u5f55\uff0c\u5e76\u4e14\u5c06label\u4f20\u7ed9nonlabel_next_level\u51fd\u6570\uff09\u3002<\/strong> <br \/> \u8fd0\u884c\u7ed3\u679c\u4e2d\u7684before\u548cafter\uff0c\u4ee3\u8868\u8fdb\u5165\u5230\u4e0b\u4e00\u5c42\u9012\u5f52\u4e4b\u524d\u548c\u4e4b\u540e\u3002\u8fd9\u91cc\u9700\u8981\u6ce8\u610f\u5f97\u662f\u8fd0\u884c\u7ed3\u679c\u4e2d\u7684<code>0 2 before [inf, inf, 0, inf, inf, inf]<\/code>\uff0c\u8fd0\u884c\u5230\u8fd9\u91cc\uff0c\u4e4b\u524d\u5df2\u7ecf\u627e\u5230\u4e86<code>[0, 1, 3, 5] [0, 1, 4, 5]<\/code>\u8fd9\u4e24\u6761\u589e\u5e7f\u8def\u5f84\uff0c\u53ef\u4ee5\u770b\u51fa\uff0c\u5728\u6df1\u5ea6\u9012\u5f52\uff0c0\u52301\u91cc\u9762\u7684\u589e\u5e7f\u8def\u5f84\u5df2\u7ecf\u627e\u5b8c\uff0c\u8fd9\u65f6\u9012\u5f52\u56de\u52300\u52302\uff0c\u4f46\u8fd0\u884c\u7ed3\u679c\u91cc<code>0 2 before [inf, inf, 0, inf, inf, inf]<\/code>\u5374\u6ca1\u6709\u628a\u524d\u9a71\u6570\u7ec4\u7684\u91cc\u9762\u76841\u7d22\u5f15\u6807\u8bb0\uff08\u6309\u7167\u4e0a\u4e00\u6bb5\u7684\u601d\u60f3\uff0c\u8fdb\u5165\u5230\u4e86\u7b2c1\u5c42\uff0c\u5c31\u5e94\u8be5\u628a1\u7d22\u5f15\u548c2\u7d22\u5f15\u90fd\u6807\u8bb0\u4e86\uff0c\u56e0\u4e3a12\u7d22\u5f15\u662f\u5c42\u6b21\u56fe\u4e2d\u7684\u7b2c1\u5c42\uff0c\u5e94\u8be5\u662f\u8981\u628a\u8fd9\u4e00\u5c42\u90fd\u6807\u8bb0\uff09\uff0c\u4f46\u5b9e\u9645\u4e0a\uff0c\u8fd9\u91cc\u4e0d\u9700\u8981\u6807\u8bb01\u7d22\u5f15\uff0c\u56e0\u4e3a\u9012\u5f52\u5185\u90e8\u662f\u5faa\u73af\u6765\u5206\u7684\u5206\u652f\uff0c\u800c0\u52301\u8fd9\u4e2a\u5206\u652f\u5df2\u7ecf\u6267\u884c\u8fc7\u4e86\uff0c\u6240\u4ee5\u5c31\u7b97\u8fd9\u91cc1\u7d22\u5f15\u6ca1\u6709\u6807\u8bb0\uff0c\u4e5f\u4e0d\u4f1a\u8d700\u52301\u8fd9\u4e2a\u5206\u652f\u4e86\u3002 <br \/> \u603b\u7ed3\u5c31\u662f\uff0c\u6b64\u4ee3\u7801\u8d39\u4e86\u597d\u591a\u8111\u7ec6\u80de\uff0c\u5982\u679c\u5df2\u7ecf\u6709\u4e86\u597d\u601d\u8def\uff0c\u8fd8\u662f\u6309\u7167\u597d\u601d\u8def\u7f16\u7a0b\u5427\u3002\u4f60\u4eec\u8981\u662f\u7406\u89e3\u4e86\u6b63\u5e38\u7684\u4ee3\u7801\u5b9e\u73b0\uff0c\u7406\u89e3\u8fd9\u53e6\u4e00\u79cd\u4ee3\u7801\u5b9e\u73b0\u5e94\u8be5\u4e5f\u4e0d\u96be\u3002\u6b64\u4ee3\u7801\u5b9e\u73b0\u7684\u4ee3\u7801\u91cf\u6bd4\u4e0a\u4e00\u79cd\u7684\u5c11\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e0a\u6765\u8bf4\u4e5f\u6bd4\u4e0a\u4e00\u79cd\u5c0f\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"\u6700\u5927\u6d41\u7b97\u6cd5\u590d\u6742\u5ea6_\u6700\u5c0f\u6d41\u7b97\u6cd5\u95ee\u9898\u5b9a\u4e49\u7ed9\u5b9a\u6709\u5411\u56feG=(V,E)\uff0c\u5176\u6bcf\u6761\u8fb9\u90fd\u6709\u5bb9\u91cfcv,wcv,wc_{v,w}.\u8fd9\u4e2a\u5bb9\u91cf\u4ee3\u8868\u8fd9\u4e2a\u8fb9\u53ef\u4ee5\u901a\u8fc7\u7684\u6700...","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/6358"}],"collection":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/comments?post=6358"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/6358\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=6358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=6358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=6358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}