{"id":568,"date":"2011-05-02T00:04:44","date_gmt":"2011-05-01T16:04:44","guid":{"rendered":"http:\/\/comzyh.tk\/blog\/?p=568"},"modified":"2017-05-03T17:40:15","modified_gmt":"2017-05-03T09:40:15","slug":"%e7%bd%91%e7%bb%9c%e6%b5%81%e5%85%a5%e9%97%a8%e2%80%94%e7%94%a8%e4%ba%8e%e6%9c%80%e5%a4%a7%e6%b5%81%e7%9a%84dinic%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/comzyh.com\/blog\/archives\/568\/","title":{"rendered":"\u7f51\u7edc\u6d41\u5165\u95e8\u2014\u7528\u4e8e\u6700\u5927\u6d41\u7684Dinic\u7b97\u6cd5"},"content":{"rendered":"<blockquote><p><strong>\u201c\u7f51\u7edc\u6d41\u535a\u5927\u7cbe\u6df1\u201d<\/strong>\u2014sideman\u8bed<br \/>\n<figure id=\"attachment_572\" aria-describedby=\"caption-attachment-572\" style=\"width: 250px\" class=\"wp-caption alignright\"><a rel=\"attachment wp-att-572\" href=\"\/\/comzyh.com\/blog\/archives\/568\/ditch-2\/\"><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"572\" data-permalink=\"https:\/\/comzyh.com\/blog\/archives\/568\/ditch-2\/\" data-orig-file=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/2011\/05\/ditch1.png?fit=250%2C250&amp;ssl=1\" data-orig-size=\"250,250\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"Drainage Ditches \" data-image-description=\"\" data-image-caption=\"&lt;p&gt;\u4e00\u4e2a\u57fa\u672c\u7684\u7f51\u7edc\u6d41\u95ee\u9898&lt;\/p&gt;\n\" data-medium-file=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/2011\/05\/ditch1.png?fit=250%2C250&amp;ssl=1\" data-large-file=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/2011\/05\/ditch1.png?fit=250%2C250&amp;ssl=1\" class=\"size-full wp-image-572\" title=\"Drainage Ditches \" src=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/\/wordpress\/2011\/05\/ditch1.png?resize=250%2C250\" alt=\"Drainage Ditches\" width=\"250\" height=\"250\" data-recalc-dims=\"1\" \/><\/a><figcaption id=\"caption-attachment-572\" class=\"wp-caption-text\">\u4e00\u4e2a\u57fa\u672c\u7684\u7f51\u7edc\u6d41\u95ee\u9898<\/figcaption><\/figure><br \/>\n\u611f\u8c22WHD\u7684\u5927\u529b\u652f\u6301<\/p><\/blockquote>\n<p>\u6700\u65e9\u77e5\u9053\u7f51\u7edc\u6d41\u7684\u5185\u5bb9\u4fbf\u662f\u6700\u5927\u6d41\u95ee\u9898\uff0c\u6700\u5927\u6d41\u95ee\u9898\u5f88\u597d\u7406\u89e3\uff1a<\/p>\n<p>\u89e3\u91ca\u4e00\u5b9a\u8981\u901a\u4fd7!<\/p>\n<p>\u5982\u53f3\u56fe\u6240\u793a,\u6709\u4e00\u4e2a\u7ba1\u9053\u7cfb\u7edf,\u8282\u70b9{1,2,3,4},\u6709\u5411\u7ba1\u9053{A,B,C,D,E},\u5373\u6709\u5411\u56fe\u4e00\u5f20. [1]\u662f<strong>\u6e90\u70b9<\/strong>,\u6709\u65e0\u9650\u7684\u6c34\u91cf,[4]\u662f<strong>\u6c47\u70b9<\/strong>,\u7ba1\u9053\u5bb9\u91cf\u5982\u56fe\u6240\u793a.\u8bd5\u95ee[4]\u70b9\u6700\u5927\u53ef\u63a5\u6536\u7684\u6c34\u7684\u6d41\u91cf?<\/p>\n<p>\u8fd9\u4fbf\u662f\u7b80\u5355\u7684<strong>\u6700\u5927\u6d41<\/strong>\u95ee\u9898,\u663e\u7136[4]\u70b9\u7684\u6700\u5927\u6d41\u91cf\u4e3a50<\/p>\n<p>\u6b7b\u7406\u6027\u6d3e\u8bf7\u6ce8\u610f:<strong>\u6d41\u91cf<\/strong>\u662f\u5355\u4f4d\u65f6\u95f4\u5185\u7684,\u603b\u53ef\u4ee5\u4e86\u5427!<\/p>\n<p>\u7136\u800c\u5bf9\u4e8e\u590d\u6742\u56fe\u7684\u6700\u5927\u6d41\u65b9\u6cd5\u662f\u4ec0\u4e48\u5462,\u6709EK,Dinic,SAP,etc.\u4e0b\u9762\u4ecb\u7ecdDinic\u7b97\u6cd5(<a href=\"\/\/comzyh.com\/blog\/archives\/568\/#Dinic-Code\">\u770b\u4ee3\u7801\u7684\u76f4\u63a5\u70b9\u8fd9<\/a>)<br \/>\n<!--more--><\/p>\n<h2>Dinic \u7b97\u6cd5<\/h2>\n<h6>Dinic\u7b97\u6cd5\u7684\u57fa\u672c\u601d\u8def:<\/h6>\n<blockquote>\n<ol>\n<li>\u6839\u636e\u6b8b\u91cf\u7f51\u7edc\u8ba1\u7b97\u5c42\u6b21\u56fe\u3002<\/li>\n<li>\u5728\u5c42\u6b21\u56fe\u4e2d\u4f7f\u7528DFS\u8fdb\u884c\u589e\u5e7f\u76f4\u5230\u4e0d\u5b58\u5728\u589e\u5e7f\u8def<\/li>\n<li>\u91cd\u590d\u4ee5\u4e0a\u6b65\u9aa4\u76f4\u5230\u65e0\u6cd5\u589e\u5e7f<\/li>\n<\/ol>\n<\/blockquote>\n<p>\u5f15\u81ea<a title=\"NOCOW\u7684\u89e3\u91ca\" href=\"http:\/\/www.nocow.cn\/index.php\/Dinic#.E7.AE.97.E6.B3.95.E6.B5.81.E7.A8.8B\" target=\"_blank\">NOCOW<\/a>,\u76f8\u5f53\u7b80\u5355\u662f\u5427&#8230;<\/p>\n<h6>\u5c0f\u8d34\u58eb:<\/h6>\n<p>\u4e00\u822c\u60c5\u51b5\u4e0b\u5728Dinic\u7b97\u6cd5\u4e2d,\u6211\u4eec\u53ea\u8bb0\u5f55\u67d0\u4e00\u8fb9\u7684<strong>\u5269\u4f59\u6d41\u91cf<\/strong>.<\/p>\n<ul>\n<li>\u6b8b\u91cf\u7f51\u7edc:\u5305\u542b<strong>\u53cd\u5411\u5f27<\/strong>\u7684\u6709\u5411\u56fe,Dinic\u8981\u5faa\u73af\u7684,\u6bcf\u6b21<strong>\u4fee\u6539\u8fc7<\/strong>\u7684\u56fe\u90fd\u662f\u6b8b\u91cf\u7f51\u7edc,<\/li>\n<li>\u5c42\u6b21\u56fe:\u5206\u5c42\u56fe,\u4ee5[<strong>\u4ece\u539f\u70b9\u5230\u67d0\u70b9\u7684\u6700\u77ed\u8ddd\u79bb<\/strong>]\u5206\u5c42\u7684\u56fe,\u8ddd\u79bb\u76f8\u7b49\u7684\u4e3a\u4e00\u5c42,(\u6bd4\u5982\u4e0a\u56fe\u7684\u5206\u5c42\u4e3a{1},{2,4},{3})<\/li>\n<li>DFS:\u8fd9\u4e2a\u5c31\u4e0d\u7528\u8bf4\u4e86\u5427&#8230;<\/li>\n<li>\u589e\u5e7f\u00a0 :\u5728\u73b0\u6709\u6d41\u91cf\u57fa\u7840\u4e0a\u53d1\u73b0\u65b0\u7684\u8def\u5f84,\u6269\u5927\u53d1\u73b0\u7684\u6700\u5927\u6d41\u91cf(<span style=\"color: #ff0000;\"><strong>\u6ce8\u610f<\/strong><\/span>:\u589e\u52a0\u91cf\u4e0d\u4e00\u5b9a\u662f\u8fd9\u6761\u8def\u5f84\u7684\u6d41\u91cf,\u800c\u662f\u65b0\u7684\u6d41\u91cf\u4e0e\u4e0a\u6b21\u6d41\u91cf\u4e4b\u5dee)<\/li>\n<li>\u589e\u5e7f\u8def:\u5728\u73b0\u6709\u6d41\u91cf\u57fa\u7840\u4e0a\u53d1\u73b0\u7684\u65b0\u8def\u5f84.(\u5feb\u6765\u627e\u832c,\u548c\u4e0a\u4e00\u6761\u6709\u4f55\u4e0d\u540c?)<\/li>\n<li>\u5269\u4f59\u6d41\u91cf:\u5f53\u4e00\u6761\u8fb9\u88ab\u589e\u5e7f\u4e4b\u540e(\u5373\u5b83\u662f\u589e\u5e7f\u8def\u7684\u4e00\u90e8\u5206,\u6216\u8005\u8bf4\u589e\u5e7f\u8def\u901a\u8fc7\u8fd9\u6761\u8fb9),\u8fd9\u6761\u8fb9\u8fd8\u80fd\u901a\u8fc7\u7684\u6d41\u91cf.<\/li>\n<li>\u53cd\u5411\u5f27:\u6211\u4eec\u5728Dinic\u7b97\u6cd5\u4e2d,\u5bf9\u4e8e\u4e00\u6761\u6709\u5411\u8fb9,\u6211\u4eec\u9700\u8981\u5efa\u7acb\u53e6\u4e00\u6761\u53cd\u5411\u8fb9(\u5f27),\u5f53\u6b63\u5411(\u8f93\u5165\u6570\u636e)\u8fb9\u5269\u4f59\u6d41\u91cf\u51cf\u5c11I\u65f6,\u53cd\u5411\u5f27\u5269\u4f59\u6d41\u91cf\u589e\u52a0I<\/li>\n<\/ul>\n<h6>Comzyh\u7684\u8f83\u8be6\u7ec6\u89e3\u91ca(\u6d41\u7a0b) :<\/h6>\n<figure id=\"attachment_567\" aria-describedby=\"caption-attachment-567\" style=\"width: 324px\" class=\"wp-caption alignright\"><br \/>\n<object classid=\"clsid:d27cdb6e-ae6d-11cf-96b8-444553540000\" width=\"324\" height=\"216\" codebase=\"http:\/\/download.macromedia.com\/pub\/shockwave\/cabs\/flash\/swflash.cab#version=6,0,40,0\"><param name=\"quality\" value=\"high\" \/><param name=\"SCALE\" value=\"exactfit\" \/><param name=\"src\" value=\"\/\/comzyh.com\/upload\/\/wordpress\/\/2011\/05\/Dinic_Example.swf\" \/><\/object><br \/>\n<figcaption id=\"caption-attachment-567\" class=\"wp-caption-text\">Dinic\u52a8\u753b\u6f14\u793a<\/figcaption><\/figure>\n<ol>\n<li>\u7528BFS\u5efa\u7acb\u5206\u5c42\u56fe\u00a0 \u6ce8\u610f:\u5206\u5c42\u56fe\u662f\u4ee5\u5f53\u524d\u56fe\u4e3a\u57fa\u7840\u5efa\u7acb\u7684,\u6240\u4ee5\u8981\u91cd\u590d\u5efa\u7acb\u5206\u5c42\u56fe<\/li>\n<li>\u7528DFS\u7684\u65b9\u6cd5\u5bfb\u627e<span style=\"color: #ff0000;\"><strong>\u4e00\u6761<\/strong><\/span>\u7531\u6e90\u70b9\u5230\u6c47\u70b9\u7684\u8def\u5f84,\u83b7\u5f97\u8fd9\u6761\u8def\u5f84\u7684\u6d41\u91cfI \u6839\u636e\u8fd9\u6761\u8def\u5f84\u4fee\u6539\u6574\u4e2a\u56fe,\u5c06\u6240\u7ecf\u4e4b\u5904\u6b63\u5411\u8fb9\u6d41\u91cf\u51cf\u5c11I,<strong>\u53cd\u5411\u8fb9\u6d41\u91cf\u589e\u52a0I<\/strong>,\u6ce8\u610fI\u662f\u975e\u8d1f\u6570<\/li>\n<li>\u91cd\u590d\u6b65\u9aa42,\u76f4\u5230DFS\u627e\u4e0d\u5230\u65b0\u7684\u8def\u5f84\u65f6,\u91cd\u590d\u6b65\u9aa41<\/li>\n<\/ol>\n<p><strong>\u6ce8\u610f<\/strong>(\u53ef\u4ee5\u65e0\u89c6):<\/p>\n<ul>\n<li>Dinic(\u5176\u5b9e\u5176\u4ed6\u7684\u597d\u591a)\u7b97\u6cd5\u4e2d\u5bfb\u627e\u5230\u589e\u5e7f\u8def\u540e\u8981\u5c06\u53cd\u5411\u8fb9\u589e\u52a0I<\/li>\n<li>Dinic\u4e2dDFS\u65f6\u53ea\u5728\u5206\u5c42\u56fe\u4e2dDFS\uff0c\u610f\u601d\u662f\u8bf4DFS\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\u7684Dis(\u8ddd\u6e90\u70b9\u7684\u8ddd\u79bb)\u8981\u6bd4\u81ea\u5df1\u7684Dis\u59271,\u4f8b\u5982\u5728\u56fe1\u4e2d\u7b2c\u4e00\u4e2a\u6b21DFS\u4e2d,1-&gt;2-&gt;4 \u8fd9\u6761\u8def\u5f84\u662f\u4e0d\u5408\u6cd5\u7684,\u56e0\u4e3aDis[2]=1;Dis[4]=1;<\/li>\n<li>\u6b65\u9aa42\u4e2d<strong>&#8220;\u83b7\u5f97\u8fd9\u6761\u8def\u5f84\u7684\u6d41\u91cf<\/strong>I &#8220;\u5b9e\u73b0:DFS\u51fd\u6570\u6709\u53c2\u91cf<strong>low<\/strong>,\u4ee3\u8868\u4ece\u6e90\u70b9\u5230\u73b0\u5728\u6700\u7a84\u7684(<strong>\u5269\u4f59\u6d41\u91cf\u6700\u5c0f<\/strong>)\u7684\u8fb9\u7684\u5269\u4f59\u6d41\u91cf,\u5f53DFS\u5230\u6c47\u70b9\u662f,Low\u4fbf\u662f\u6211\u4eec\u8981\u7684\u6d41\u91cfI<\/li>\n<\/ul>\n<h6>\u5bf9\u4e8e\u53cd\u5411\u5f27(\u53cd\u5411\u8fb9)\u7684\u7406\u89e3:<\/h6>\n<p>\u8fd9\u4e00\u6bb5\u4e0d\u7406\u89e3\u4e5f\u4e0d\u662f\u4e0d\u53ef\u4ee5,\u5bf9\u4e8e\u4f1a\u5199\u7b97\u6cd5\u6ca1\u4ec0\u4e48\u5e2e\u52a9,\u5982\u679c\u4f60\u7740\u6025,\u76f4\u63a5\u65e0\u89c6\u5373\u53ef.<br \/>\n\u5148\u4e3e\u4e00\u4e2a\u4f8b\u5b50(\u5982\u53f3\u56fe):<\/p>\n<figure id=\"attachment_573\" aria-describedby=\"caption-attachment-573\" style=\"width: 259px\" class=\"wp-caption alignright\"><a rel=\"attachment wp-att-573\" href=\"\/\/comzyh.com\/blog\/archives\/568\/netflow1\/\"><img loading=\"lazy\" decoding=\"async\" data-attachment-id=\"573\" data-permalink=\"https:\/\/comzyh.com\/blog\/archives\/568\/netflow1\/\" data-orig-file=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/2011\/05\/NetFlow1.png?fit=324%2C216&amp;ssl=1\" data-orig-size=\"324,216\" data-comments-opened=\"1\" data-image-meta=\"{&quot;aperture&quot;:&quot;0&quot;,&quot;credit&quot;:&quot;&quot;,&quot;camera&quot;:&quot;&quot;,&quot;caption&quot;:&quot;&quot;,&quot;created_timestamp&quot;:&quot;0&quot;,&quot;copyright&quot;:&quot;&quot;,&quot;focal_length&quot;:&quot;0&quot;,&quot;iso&quot;:&quot;0&quot;,&quot;shutter_speed&quot;:&quot;0&quot;,&quot;title&quot;:&quot;&quot;}\" data-image-title=\"\u5fc5\u987b\u4f7f\u7528\u53cd\u5411\u5f27\u7684\u6d41\u7f51\u7edc\" data-image-description=\"&lt;p&gt;\u5fc5\u987b\u4f7f\u7528\u53cd\u5411\u5f27\u7684\u6d41\u7f51\u7edc&lt;\/p&gt;\n\" data-image-caption=\"&lt;p&gt;\u5fc5\u987b\u4f7f\u7528\u53cd\u5411\u5f27\u7684\u6d41\u7f51\u7edc&lt;\/p&gt;\n\" data-medium-file=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/2011\/05\/NetFlow1.png?fit=324%2C216&amp;ssl=1\" data-large-file=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/wordpress\/\/2011\/05\/NetFlow1.png?fit=324%2C216&amp;ssl=1\" class=\"size-full wp-image-573 \" title=\"\u5fc5\u987b\u4f7f\u7528\u53cd\u5411\u5f27\u7684\u6d41\u7f51\u7edc\" src=\"https:\/\/i0.wp.com\/comzyh.com\/upload\/\/wordpress\/2011\/05\/NetFlow1.png?resize=259%2C173\" alt=\"\u5fc5\u987b\u4f7f\u7528\u53cd\u5411\u5f27\u7684\u6d41\u7f51\u7edc\" width=\"259\" height=\"173\" data-recalc-dims=\"1\" \/><\/a><figcaption id=\"caption-attachment-573\" class=\"wp-caption-text\">\u5fc5\u987b\u4f7f\u7528\u53cd\u5411\u5f27\u7684\u6d41\u7f51\u7edc<\/figcaption><\/figure>\n<p>\u5728\u8fd9\u5e45\u56fe\u4e2d\u6211\u4eec\u9996\u5148\u8981\u589e\u5e7f1-&gt;2-&gt;4-&gt;6,\u8fd9\u65f6\u53ef\u4ee5\u83b7\u5f97\u4e00\u4e2a\u5bb9\u91cf\u4e3a2\u7684\u6d41,\u4f46\u662f\u5982\u679c\u4e0d\u5efa\u7acb4-&gt;2\u53cd\u5411\u5f27\u7684\u8bdd,\u5219\u65e0\u6cd5\u8fdb\u4e00\u6b65\u589e\u5e7f,\u6700\u7ec8\u7b54\u6848\u4e3a2,\u663e\u7136\u662f\u4e0d\u5bf9\u7684,\u7136\u800c\u5982\u679c\u5efa\u7acb\u4e86\u53cd\u5411\u5f274-&gt;2,\u5219\u7b2c\u4e8c\u6b21\u80fd\u8fdb\u884c1-&gt;3-&gt;4-&gt;2-&gt;5-&gt;6\u7684\u589e\u5e7f,\u6700\u5927\u6d41\u4e3a3.<\/p>\n<p>Comzyh\u5bf9\u53cd\u5411\u5f27\u7684\u7406\u89e3\u53ef\u4ee5\u8bf4\u662f&#8221;<strong>\u5077\u6881\u6362\u67f1<\/strong>&#8220;,\u8bf7<span style=\"color: #ff0000;\">\u4ed4\u7ec6\u9605\u8bfb<\/span>:\u5728\u4e0a\u9762\u7684\u4f8b\u5b50\u4e2d,\u6211\u4eec\u53ef\u4ee5\u770b\u51fa,\u6700\u7ec8\u7ed3\u679c\u662f1-&gt;2-&gt;5-&gt;6\u548c1-&gt;2-&gt;4-&gt;6\u548c1-&gt;3-&gt;4-&gt;6.\u5f53\u589e\u5e7f\u5b8c1-&gt;2-&gt;4-&gt;5(\u4ee3\u53f7A)\u540e,\u5728\u589e\u5e7f1-&gt;3-&gt;4-&gt;2-&gt;5-&gt;6(\u4ee3\u53f7B),\u76f8\u5f53\u4e8e\u5c06\u7ecf\u8fc7\u8282\u70b9<span style=\"color: #ff0000;\">2<\/span>\u7684A\u6d41\u4ece\u4e2d\u622a\u6d411(\u603b\u5171\u662f2)\u8d702-&gt;5&gt;6,\u800c\u4e0d\u8d702-&gt;4&gt;6\u4e86,\u540c\u65f6B\u6d41\u4e5f\u4ece\u8282\u70b9<span style=\"color: #ff0000;\">4<\/span>\u622a\u6d41\u51fa1(\u603b\u5171\u662f1)\u8d704-&gt;6\u800c\u4e0d\u662f4-&gt;2-&gt;5-&gt;6,\u76f8\u5f53\u4e8eAB\u6d41\u505a\u52a0\u6cd5.<\/p>\n<p>\u7b80\u5355\u7684\u8bf4\u53cd\u5411\u5f27\u4e3a\u4eca\u540e\u63d0\u4f9b\u53cd\u6094\u7684\u673a\u4f1a,\u8ba9\u524d\u9762\u4e0d\u8d70\u8fd9\u6761\u8def\u800c\u8d70\u522b\u7684\u8def.<\/p>\n<p>Alwa\u540c\u5b66\u975e\u8981\u6211\u7ed9\u4ed6\u7684\u6587\u7ae0\u52a0\u4e00\u4e2a\u94fe\u63a5,\u5927\u5bb6\u53ef\u4ee5\u770b\u770b\u4ed6\u7684\u6587\u7ae0:\u00a0<a title=\"\u6709\u5173\u7f51\u7edc\u6d41\u4e2d\u7684\u53cd\u5411\u5f27\u548c\u589e\u5e7f\u8def\" href=\"http:\/\/alwa.name\/blog\/?p=585\" target=\"_blank\" class=\"broken_link\">\u6709\u5173\u7f51\u7edc\u6d41\u4e2d\u7684\u53cd\u5411\u5f27\u548c\u589e\u5e7f\u8def<\/a><br \/>\n<a name=\"Dinic-Code\"><\/a><\/p>\n<h6>Dinic\u7b97\u6cd5\u7684\u7a0b\u5e8f\u5b9e\u73b0<\/h6>\n<p>\u6700\u5927\u6d41\u7b97\u6cd5\u4e00\u76f4\u6709\u4e00\u4e2a\u5165\u95e8\u7ecf\u5178\u9898:<a title=\"POJ 1273\" href=\"http:\/\/poj.org\/problem?id=1273\" target=\"_blank\">POJ 1273<\/a> \u6216\u8005\u662f<a href=\"http:\/\/www.nocow.cn\/index.php\/Translate:USACO\/ditch\" target=\"_blank\">UCACO 4_2_1 \u6765\u81eaNOCOW(\u4e2d\u6587)<\/a> \u8fd9\u4e24\u4e2a\u662f\u540c\u4e00\u4e2a\u9898<\/p>\n<p>\u7ed9\u51fa\u8fd9\u9053\u9898\u7684\u4ee3\u7801<\/p>\n<pre lang=\"cpp\">\n\/*\nProgram:POJ 1273 \/\nDinic\nAuthor:Comzyh\n*\/\n#include <cstdio>\n#include <cstring>\n#include <cstdlib>\n#include <iostream>\n#define min(x,y) ((x<y)?(x):(y))\nusing namespace std;\nconst int MAX=0x5fffffff;\/\/\nint tab[250][250];\/\/\u90bb\u63a5\u77e9\u9635 \nint dis[250];\/\/\u8ddd\u6e90\u70b9\u8ddd\u79bb,\u5206\u5c42\u56fe \nint q[2000],h,r;\/\/BFS\u961f\u5217 ,\u9996,\u5c3e \nint N,M,ANS;\/\/N:\u70b9\u6570;M,\u8fb9\u6570 \nint BFS()\n{\n     int i,j;\n     memset(dis,0xff,sizeof(dis));\/\/\u4ee5-1\u586b\u5145 \n     dis[1]=0;\n     h=0;r=1;\n     q[1]=1;\n     while (h<r)\n     {\n           j=q[++h];\n           for (i=1;i<=N;i++)\n               if (dis[i]<0 &#038;&#038; tab[j][i]>0)\n               {\n                  dis[i]=dis[j]+1; \n                  q[++r]=i;\n               }\n     }\n     if (dis[N]>0)\n        return 1;\n     else\n        return 0;\/\/\u6c47\u70b9\u7684DIS\u5c0f\u4e8e\u96f6,\u8868\u660eBFS\u4e0d\u5230\u6c47\u70b9 \n}\n\/\/Find\u4ee3\u8868\u4e00\u6b21\u589e\u5e7f,\u51fd\u6570\u8fd4\u56de\u672c\u6b21\u589e\u5e7f\u7684\u6d41\u91cf,\u8fd4\u56de0\u8868\u793a\u65e0\u6cd5\u589e\u5e7f \nint find(int x,int low)\/\/Low\u662f\u6e90\u70b9\u5230\u73b0\u5728\u6700\u7a84\u7684(\u5269\u4f59\u6d41\u91cf\u6700\u5c0f)\u7684\u8fb9\u7684\u5269\u4f59\u6d41\u91cf\n{\n    int i,a=0;\n    if (x==N)return low;\/\/\u662f\u6c47\u70b9 \n    for (i=1;i<=N;i++)\n    if (tab[x][i] >0 \/\/\u8054\u901a \n     && dis[i]==dis[x]+1 \/\/\u662f\u5206\u5c42\u56fe\u7684\u4e0b\u4e00\u5c42 \n     &&(a=find(i,min(low,tab[x][i]))))\/\/\u80fd\u5230\u6c47\u70b9(a <> 0) \n    {\n       tab[x][i]-=a;\n       tab[i][x]+=a;\n       return a;\n    }\n    return 0;\n    \n}\nint main()\n{\n    \/\/freopen(\"ditch.in\" ,\"r\",stdin );\n    \/\/freopen(\"ditch.out\",\"w\",stdout);\n    int i,j,f,t,flow,tans;\n    while (scanf(\"%d%d\",&M,&N)!=EOF){\n    memset(tab,0,sizeof(tab));\n    for (i=1;i<=M;i++)\n    {\n        scanf(\"%d%d%d\",&#038;f,&#038;t,&#038;flow);\n        tab[f][t]+=flow;\n    }\n    \/\/\n    ANS=0;\n    while (BFS())\/\/\u8981\u4e0d\u505c\u5730\u5efa\u7acb\u5206\u5c42\u56fe,\u5982\u679cBFS\u4e0d\u5230\u6c47\u70b9\u624d\u7ed3\u675f \n    {\n          while(tans=find(1,0x7fffffff))ANS+=tans;\/\/\u4e00\u6b21BFS\u8981\u4e0d\u505c\u5730\u627e\u589e\u5e7f\u8def,\u76f4\u5230\u627e\u4e0d\u5230\u4e3a\u6b62 \n    }\n    printf(\"%d\\n\",ANS);\n    }\n    system(\"pause\");\n}\n\n<\/pre>\n<p>\u53e6\u4e00\u9053\u9898\u76ee\u662f POJ 1459 \u4f7f\u7528\u90bb\u63a5\u8868\uff0c\u91c7\u7528\u5f53\u524d\u5f27\u4f18\u5316<\/p>\n<pre lang=\"cpp\">\n#include <iostream>\n#include <cstdio>\n#include <cstring>\n#include <vector>\n#include <queue>\nusing namespace std;\nint N, NP, NC, M;\nstruct Edge\n{\n    int u, v, cap;\n    Edge() {}\n    Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}\n} es[150 * 150];\nint R, S, T;\nvector<int> tab[109]; \/\/ \u8fb9\u96c6\nint dis[109];\nint current[109];\nvoid addedge(int u, int v, int cap)\n{\n    tab[u].push_back(R);\n    es[R++] = Edge(u, v, cap); \/\/ \u6b63\u5411\u8fb9\n    tab[v].push_back(R);\n    es[R++] = Edge(v, u, 0); \/\/ \u53cd\u5411\u8fb9\u5bb9\u91cf\u4e3a0\n    \/\/ \u6b63\u5411\u8fb9\u4e0b\u6807\u901a\u8fc7\u5f02\u6216\u5c31\u5f97\u5230\u53cd\u5411\u8fb9\u4e0b\u6807, 2 ^ 1 == 3 ; 3 ^ 1 == 2\n}\nint BFS()\n{\n    queue<int> q;\n    q.push(S);\n    memset(dis, 0x3f, sizeof(dis));\n    dis[S] = 0;\n    while (!q.empty())\n    {\n        int h = q.front();\n        q.pop();\n        for (int i = 0; i < tab[h].size(); i++)\n        {\n            Edge &#038;e = es[tab[h][i]];\n            if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)\n            {\n                dis[e.v] = dis[h] + 1;\n                q.push(e.v);\n            }\n        }\n    }\n    return dis[T] < 0x3f3f3f3f; \/\/ \u8fd4\u56de\u662f\u5426\u80fd\u591f\u5230\u8fbe\u6c47\u70b9\n}\nint dinic(int x, int maxflow)\n{\n    if (x == T)\n        return maxflow;\n    \/\/ i = current[x] \u5f53\u524d\u5f27\u4f18\u5316\n    for (int i = current[x]; i < tab[x].size(); i++)\n    {\n        current[x] = i;\n        Edge &#038;e = es[tab[x][i]];\n        if (dis[e.v] == dis[x] + 1 &#038;&#038; e.cap > 0)\n        {\n            int flow = dinic(e.v, min(maxflow, e.cap));\n            if (flow)\n            {\n                e.cap -= flow; \/\/ \u6b63\u5411\u8fb9\u6d41\u91cf\u964d\u4f4e\n                es[tab[x][i] ^ 1].cap += flow; \/\/ \u53cd\u5411\u8fb9\u6d41\u91cf\u589e\u52a0\n                return flow;\n            }\n        }\n    }\n    return 0; \/\/ \u627e\u4e0d\u5230\u589e\u5e7f\u8def \u9000\u51fa\n}\nint DINIC()\n{\n    int ans = 0;\n\n    while (BFS()) \/\/ \u5efa\u7acb\u5206\u5c42\u56fe\n    {\n        int flow;\n        memset(current, 0, sizeof(current)); \/\/ BFS\u540e\u5e94\u5f53\u6e05\u7a7a\u5f53\u524d\u5f27\u6570\u7ec4\n        while (flow = dinic(S, 0x3f3f3f3f)) \/\/ \u4e00\u6b21BFS\u53ef\u4ee5\u8fdb\u884c\u591a\u6b21\u589e\u5e7f\n            ans += flow;\n    }\n    return ans;\n}\nint main()\n{\n    while (scanf(\"%d%d%d%d\", &N, &NP, &NC, &M) != EOF)\n    {\n        R = 0;\n        S = N;\n        T = N + 1;\n        for (int i = 0; i <= T; i++)\n            tab[i].clear();\n        for (int i = 0; i < M; i++)\n        {\n            int u, v, cap;\n            scanf(\" (%d,%d)%d\", &#038;u, &#038;v, &#038;cap);\n            addedge(u, v, cap);\n        }\n        for (int i = 0; i < NP; i++)\n        {\n            int u, p;\n            scanf(\" (%d)%d\", &#038;u, &#038;p);\n            addedge(S, u, p);\n        }\n        for (int i = 0; i < NC; i++)\n        {\n            int u, c;\n            scanf(\" (%d)%d\", &#038;u, &#038;c);\n            addedge(u, T, c);\n        }\n\n        printf(\"%d\\n\", DINIC());\n    }\n    return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u201c\u7f51\u7edc\u6d41\u535a\u5927\u7cbe\u6df1\u201d\u2014sideman\u8bed \u611f\u8c22WHD\u7684\u5927\u529b\u652f\u6301 \u6700\u65e9\u77e5\u9053\u7f51\u7edc\u6d41\u7684\u5185\u5bb9\u4fbf\u662f\u6700\u5927\u6d41\u95ee\u9898\uff0c\u6700\u5927\u6d41\u95ee\u9898\u5f88\u597d [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[9],"tags":[],"class_list":["post-568","post","type-post","status-publish","format-standard","hentry","category-9"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6XQWE-9a","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/568","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=568"}],"version-history":[{"count":9,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/568\/revisions"}],"predecessor-version":[{"id":979,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/568\/revisions\/979"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=568"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=568"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=568"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}