{"id":276,"date":"2011-12-04T09:22:13","date_gmt":"2011-12-04T09:22:13","guid":{"rendered":"http:\/\/sxkdz.0ginr.com\/blog\/?p=276"},"modified":"2011-12-04T09:23:20","modified_gmt":"2011-12-04T09:23:20","slug":"%e3%80%90%e4%bb%a3%e7%a0%81%e5%ad%98%e6%a1%a3%e3%80%91edmonds-karp%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/sxkdz.0ginr.com\/blog\/?p=276","title":{"rendered":"\u3010\u4ee3\u7801\u5b58\u6863\u3011Edmonds Karp\u7b97\u6cd5"},"content":{"rendered":"<p>[cpp]<br \/>\n#include <cstdio><br \/>\n#include <algorithm><br \/>\nusing std::min;<\/p>\n<p>const int INF = 0x7ffffff;<br \/>\nint v, e, pre[205], inc[205], queue[205], g[205][205], f[205][205];<\/p>\n<p>bool bfs(int src, int des) {<br \/>\n\tint fp = 0, rp = 0;<br \/>\n\tfor (int i = 1; i <= v; ++ i) {\n\t\tpre[i] = -1;\n\t}\n\tqueue[fp] = src;\n\tinc[src] = INF;\n\twhile (fp <= rp) {\n\t\tint u = queue[fp ++];\n\t\tfor (int i = 1; i <= v; ++ i) {\n\t\t\tif ((pre[i] == -1) &#038;&#038; (f[u][i] < g[u][i])) {\n\t\t\t\tinc[i] = min(inc[u], g[u][i] - f[u][i]);\n\t\t\t\tpre[i] = u;\n\t\t\t\tif (i == des) {\n\t\t\t\t\treturn true;\n\t\t\t\t}\n\t\t\t\tqueue[++ rp] = i;\n\t\t\t}\n\t\t}\n\t}\n\treturn false;\n}\n\nint Edmonds_Karp(int src, int des) {\n\tint maxFlow = 0;\n\n\twhile (bfs(src, des)) {\n\t\tmaxFlow += inc[des];\n\t\tfor (int i = des; i != src; i = pre[i]) {\n\t\t\tf[pre[i]][i] += inc[des];\n\t\t\tf[i][pre[i]] = -f[pre[i]][i];\n\t\t}\n\t}\n\n\treturn maxFlow;\n}\n\nint main(void) {\n\n\tscanf(\"%d %d\", &#038;e, &#038;v);\n\tfor (int i = 1; i <= e; ++ i) {\n\t\tint x, y, k;\n\t\tscanf(\"%d %d %d\", &#038;x, &#038;y, &#038;k);\n\t\tg[x][y] += k;\n\t}\n\n\tprintf(\"%d\\n\", Edmonds_Karp(1, v));\n\n\treturn 0;\n}\n\n[\/cpp]\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[cpp] #include #include using std::min; const int INF = 0x7ffffff; int v, e, pre[205], inc[205], queue[205], g[205][205], f[205][205]; bool bfs(int src, int des) { int fp = 0, rp = 0; for (int i = 1; i<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[55,54,35,70,53],"class_list":["post-276","post","type-post","status-publish","format-standard","hentry","category-22","tag-edmonds_karp","tag-ek","tag-oi","tag-70","tag-53"],"_links":{"self":[{"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/276","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=276"}],"version-history":[{"count":3,"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/276\/revisions"}],"predecessor-version":[{"id":278,"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/276\/revisions\/278"}],"wp:attachment":[{"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=276"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=276"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sxkdz.0ginr.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=276"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}