{"id":53,"date":"2016-06-20T09:37:08","date_gmt":"2016-06-20T01:37:08","guid":{"rendered":"http:\/\/tyswly.com\/?p=53"},"modified":"2016-06-20T09:37:08","modified_gmt":"2016-06-20T01:37:08","slug":"%e6%b5%85%e8%b0%88%e6%9c%80%e5%b0%8f%e7%94%9f%e6%88%90%e6%a0%91","status":"publish","type":"post","link":"https:\/\/tys.fun\/?p=53","title":{"rendered":"\u6d45\u8c08\u6700\u5c0f\u751f\u6210\u6811"},"content":{"rendered":"<p>\u6837\u9898\u53ef\u89c1<a href=\"http:\/\/syzoj.com\/problem\/142\">SYZOJ<\/a><br \/>\n\u6700\u8fd1\u53d1\u73b0\u6700\u5c0f\u751f\u6210\u6811\u5c45\u7136\u5c5e\u4e8eNOIP\u8003\u5bdf\u8303\u56f4\u4e4b\u5185\uff0c\u5c31\u987a\u5e26\u819c\u4e86\u4e00\u53d1Kruscal\u3002<br \/>\nKruscal\u7684\u4e3b\u8981\u601d\u60f3\u5c31\u662f\u8d2a\u5fc3\uff0c\u8fd9\u70b9\u611f\u89c9\u8ddfDijkstra\u6709\u70b9\u50cf\uff0c\u4f46\u662f\u5e76\u4e0d\u7528\u8fdb\u884c\u5806\u4f18\u5316\u4e4b\u7c7b\u7684\u795e\u5947\u7684\u4e1c\u897f\u3002\u3002<br \/>\n<del>\u5176\u5b9e\u633a\u7b80\u5355\u7684\uff0c\u6bd4dinic\u4e0d\u77e5\u9053\u597d\u5199\u5230\u54ea\u91cc\u53bb\u4e86\u3002<\/del><\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;algorithm&gt;\n#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\nusing namespace std;\nconst int MX = 305;\nconst int inf = 1000000007;\nclass edge {\npublic:\n\tint x, y, v;\n}e[MX * MX];\nint bing[MX], c[MX];\nint n, tot;\nint find_father(int x) {\n\treturn x == bing[x] ? x : find_father(bing[x]);\n}\nbool cmp(edge a, edge b) {\n\treturn a.v &lt; b.v;\n}\nint kruscal() {\n\tsort(e + 1, e + tot + 1, cmp);\n\tint cnt = tot;\n\tint ans = 0;\n\tfor (int i = 0; i &lt;= n; i++)\tbing[i] = i;\n\tfor (int i = 1; i &lt;= tot; i++) {\n\t\tint f1 = find_father(e[i].x);\n\t\tint f2 = find_father(e[i].y);\n\t\tif (f1 != f2) {\n\t\t\tbing[f1] = f2;\n\t\t\tans += e[i].v;\n\t\t\tcnt--;\n\t\t\tif (cnt == 1)\tbreak;\n\t\t}\n\t}\n\treturn ans;\n}\nint main() {\n\tcin &gt;&gt; n;\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d\", &amp;c[i]);\n\t\te[++tot].x = 0;\n\t\te[tot].y = i;\n\t\te[tot].v = c[i];\n\t}\n\tint tmp;\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tfor (int j = 1; j &lt;= n; j++) {\n\t\t\tscanf(\"%d\", &amp;tmp);\n\t\t\tif (tmp) {\n\t\t\t\te[++tot].x = i;\n\t\t\t\te[tot].y = j;\n\t\t\t\te[tot].v = tmp;\n\t\t\t}\n\t\t}\n\t}\n\tcout &lt;&lt; kruscal() &lt;&lt; endl;\n}\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6837\u9898\u53ef\u89c1SYZOJ \u6700\u8fd1\u53d1\u73b0\u6700\u5c0f\u751f\u6210\u6811\u5c45\u7136\u5c5e\u4e8eNOIP\u8003\u5bdf\u8303\u56f4\u4e4b\u5185\uff0c\u5c31\u987a\u5e26\u819c\u4e86\u4e00\u53d1Kruscal\u3002 Krusc &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-53","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\/53","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=53"}],"version-history":[{"count":0,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/53\/revisions"}],"wp:attachment":[{"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=53"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=53"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=53"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}