{"id":50,"date":"2016-06-16T19:54:48","date_gmt":"2016-06-16T11:54:48","guid":{"rendered":"http:\/\/tyswly.com\/?p=50"},"modified":"2016-06-16T19:54:48","modified_gmt":"2016-06-16T11:54:48","slug":"usaco93drainage-ditches%e6%8e%92%e6%b0%b4%e6%b8%a0","status":"publish","type":"post","link":"https:\/\/tys.fun\/?p=50","title":{"rendered":"[USACO93]Drainage Ditches\u6392\u6c34\u6e20"},"content":{"rendered":"<p>\u9898\u76ee\u89c1<a href=\"http:\/\/syzoj.com\/problem\/143\">SYZOJ<\/a><br \/>\n\u7f51\u7edc\u6d41\u521d\u6b65\u3002<br \/>\n\u6069\uff0c\u7ecf\u5386\u5343\u8f9b\u4e07\u82e6\uff0c\u91cd\u6784\u4ee3\u7801\u65e0\u6570\u904d\u4e4b\u540e\uff0c\u7ec8\u4e8e\u628a\u7b2c\u4e00\u53d1dinic\u5b8c\u6210\u4e86\u3002<del>\u73b0\u5728\u7684\u624b\u901f\uff0c\u518d\u5199dinic\u53ea\u75287\u5206\u949f\u3002\u3002\u3002\u3002\u3002<\/del><\/p>\n<pre class=\"lang:c++ decode:true\">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;queue&gt;\n#include &lt;cstdlib&gt;\n#include &lt;cstring&gt;\nusing namespace std;\nconst int MX = 305;\nconst int INF = 100000007;\nint dis[MX], head[MX];\nint tot, s, t, m, n;\nclass edge {\npublic:\n\tint fr, to, le, ne;\n}e[MX * MX];\nvoid addedge(int a, int b, int v) {\/\/\u90bb\u63a5\u8868\u52a0\u8fb9\uff0c\u4e0d\u89e3\u91ca\u4e86\n\ttot++;\n\te[tot].fr = a;\n\te[tot].to = b;\n\te[tot].le = v;\n\te[tot].ne = head[a];\n\thead[a] = tot;\n\ttot++;\/\/\u6dfb\u52a0\u53cd\u5411\u8fb9\n\te[tot].fr = b;\n\te[tot].to = a;\n\te[tot].ne = head[b];\n\thead[b] = tot;\n}\nbool bfs() {\/\/\u6bcf\u6b21\u8fdb\u884c\u5e7f\u641c\u641c\u67e5\u627e\uff0c\u5bf9\u6b8b\u91cf\u7f51\u7edc\u8fdb\u884c\u5206\u5c42\u3002\n\tqueue &lt;int&gt; q;\n\tint now, to;\n\tmemset(dis, 0, sizeof(dis));\n\tdis[s] = 1;\n\tq.push(s);\n\twhile (!q.empty()) {\n\t\tnow = q.front();\n\t\tq.pop();\n\t\tfor (int i = head[now]; i; i = e[i].ne) {\n\t\t\tto = e[i].to;\n\t\t\tif (((!dis[to]) || dis[to] == dis[now] + 1) &amp;&amp; e[i].le) {\n\t\t\t\tdis[to] = dis[now] + 1;\n\t\t\t\tq.push(to);\n\t\t\t}\n\t\t}\n\t}\n\treturn dis[t];\n}\nint dfs(int now, int min_flow) {\/\/\u6df1\u641c\u67e5\u627e\u6700\u5927\u6d41\n\tint to, now_flow;\n\tif (now == t) {\n\t\treturn min_flow;\n\t}\n\tfor (int i = head[now]; i; i = e[i].ne) {\n\t\tto = e[i].to;\n\t\tif (dis[to] != dis[now] + 1) continue;\/\/\u4f18\u5316\uff0c\u5982\u679c\u4e0b\u4e00\u6761\u8fb9\u4e0d\u662f\u4e0b\u4e00\u5c42\uff0c\u76f4\u63a5\u8df3\u8fc7\n\t\tif (e[i].le &lt;= 0) continue;\/\/\u5982\u679c\u8fd9\u4e00\u6761\u8fb9\u5df2\u7ecf\u6ca1\u6709\u4f59\u91cf\uff0c\u8df3\u8fc7\n\t\tnow_flow = dfs(to, min(min_flow, e[i].le));\n\t\tif (!now_flow) continue;\n\t\te[i].le -= now_flow;\n\t\tif (i % 2) e[i + 1].le += now_flow;\/\/\u53cd\u5411\u8fb9\u5904\u7406\n\t\telse e[i - 1].le += now_flow;\n\t\treturn now_flow;\n\t}\n\treturn 0;\n}\nint dinic() {\n\tint ans = 0;\n\tint tmp;\n\twhile (bfs()) {\n\t\t\/\/cout &lt;&lt; \"flag\\n\";\n\t\twhile (tmp = dfs(s, INF)) ans += tmp;\n\t}\n\treturn ans;\n}\nint main() {\n\tint a, b, v;\n\tscanf(\"%d %d\", &amp;n, &amp;m);\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d%d%d\", &amp;a, &amp;b, &amp;v);\n\t\taddedge(a, b, v);\n\t}\n\ts = 1;\n\tt = m;\n\tprintf(\"%d\\n\", dinic());\n\treturn 0;\n}\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u89c1SYZOJ \u7f51\u7edc\u6d41\u521d\u6b65\u3002 \u6069\uff0c\u7ecf\u5386\u5343\u8f9b\u4e07\u82e6\uff0c\u91cd\u6784\u4ee3\u7801\u65e0\u6570\u904d\u4e4b\u540e\uff0c\u7ec8\u4e8e\u628a\u7b2c\u4e00\u53d1dinic\u5b8c\u6210\u4e86\u3002\u73b0\u5728\u7684\u624b\u901f &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-50","post","type-post","status-publish","format-standard","hentry","category-report"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/50","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=50"}],"version-history":[{"count":0,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/50\/revisions"}],"wp:attachment":[{"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=50"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=50"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=50"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}