{"id":3004,"date":"2023-06-09T06:14:29","date_gmt":"2023-06-08T22:14:29","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=3004"},"modified":"2023-06-09T06:19:45","modified_gmt":"2023-06-08T22:19:45","slug":"luogu-1954-noi2010-%e8%88%aa%e7%a9%ba%e7%ae%a1%e5%88%b6","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-1954-noi2010-%e8%88%aa%e7%a9%ba%e7%ae%a1%e5%88%b6\/","title":{"rendered":"Luogu P1954. [NOI2010] \u822a\u7a7a\u7ba1\u5236"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P1954\">https:\/\/www.luogu.com.cn\/problem\/P1954<\/a><\/li>\n<\/ul>\n<p>\u7b2c\u4e00\u95ee\u663e\u7136\u53ef\u4ee5 dag dp\uff0c\u6c42\u51fa\u6bcf\u4e2a\u70b9\u7684\u771f\u5b9e\u6700\u665a\u53d1\u8f66\u65f6\u95f4\uff0c<br \/>\n\u7136\u540e\u7528\u8fd9\u4e2a\u4e1c\u897f\u8d2a\u5fc3\u6784\u9020\u3002<\/p>\n<p>\u7b2c\u4e8c\u95ee\u8fd8\u662f\u7528\u540c\u4e00\u4e2a dp \u6570\u7ec4\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u8d2a\u5fc3\u6784\u9020\u7684\u65f6\u5019\uff0c\u6211\u4eec\u5ffd\u7565\u6240\u6709\u8be2\u95ee\u70b9\u4f20\u9012\u95ed\u5305\u91cc\u7684\u8282\u70b9\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(2e3)+9;\r\n\r\nVI adj&#x5B;N], rdj&#x5B;N]; int f&#x5B;N], k&#x5B;N], o&#x5B;N];\r\nbool vis&#x5B;N];\r\nint n, m;\r\n\r\n\r\nvoid dfs(int u = 0) {\r\n    vis&#x5B;u] = 1; f&#x5B;u] = k&#x5B;u];\r\n    for (auto v: adj&#x5B;u]) {\r\n        if (!vis&#x5B;v]) dfs(v);\r\n        checkMin(f&#x5B;u], (f&#x5B;v] ? f&#x5B;v] : k&#x5B;v]) - 1);\r\n    }\r\n}\r\n\r\nvoid rfs(int u = 0) {\r\n    vis&#x5B;u] = 1; f&#x5B;u] = 0;\r\n    for (auto v: rdj&#x5B;u])  {\r\n        if (!vis&#x5B;v]) rfs(v);\r\n    }\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n, m); REP(i, n) RD(k&#x5B;i]);\r\n\r\n    DO(m) {\r\n        int a, b; RD(a, b), a--, b--;\r\n        adj&#x5B;a].PB(b);\r\n        rdj&#x5B;b].PB(a);\r\n    }\r\n    REP(i, n) if (!vis&#x5B;i]) dfs(i); REP(i, n) o&#x5B;i] = i;\r\n\r\n    sort(o, o+n, &#x5B;](int a, int b) {\r\n         return f&#x5B;a] &lt; f&#x5B;b];\r\n    });\r\n\r\n    REP(i, n) printf(&quot;%d &quot;, o&#x5B;i]+1); puts(&quot;&quot;);\r\n\r\n    REP(i, n) {\r\n        RST(vis); rfs(i); REP(i, n) if (!vis&#x5B;i]) dfs(i);\r\n\r\n        sort(o, o+n, &#x5B;](int a, int b) {\r\n            return f&#x5B;a] &gt; f&#x5B;b];\r\n        });\r\n\r\n        int m = n-1; RST(vis);\r\n\r\n        REP(ii, n) {\r\n            int i = o&#x5B;ii]; if (!f&#x5B;i]) break;\r\n            int t = min(m, f&#x5B;i]);\r\n            while (vis&#x5B;t]) --t; vis&#x5B;t] = 1;\r\n            while (vis&#x5B;m]) --m;\r\n        }\r\n        printf(&quot;%d &quot;, m+1);\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P1954 \u7b2c\u4e00\u95ee\u663e\u7136\u53ef\u4ee5 dag dp\uff0c\u6c42\u51fa\u6bcf\u4e2a\u70b9\u7684\u771f\u5b9e\u6700\u665a\u53d1\u8f66\u65f6\u95f4\uff0c \u7136\u540e\u7528\u8fd9\u4e2a\u4e1c\u897f\u8d2a\u5fc3\u6784\u9020\u3002 \u7b2c\u4e8c\u95ee\u8fd8\u662f\u7528\u540c\u4e00\u4e2a dp \u6570\u7ec4\uff0c\u4e0d\u8fc7\u8fd9\u6b21\u8d2a\u5fc3\u6784\u9020\u7684\u65f6\u5019\uff0c\u6211\u4eec\u5ffd\u7565\u6240\u6709\u8be2\u95ee\u70b9\u4f20\u9012\u95ed\u5305\u91cc\u7684\u8282\u70b9\u3002 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = int(2e3)+9; VI adj&#x5B;N], rdj&#x5B;N]; int f&#x5B;N], k&#x5B;N], o&#x5B;N]; bool vis&#x5B;N]; int n, m; void dfs(int u = 0) { vis&#x5B;u] = 1; f&#x5B;u] = k&#x5B;u]; for (auto v: adj&#x5B;u]) { if (!vis&#x5B;v]) dfs(v); checkMin(f&#x5B;u], (f&#x5B;v] ? f&#x5B;v] : [&hellip;]<\/p>\n","protected":false},"author":1,"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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-3004","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Ms","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3004","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=3004"}],"version-history":[{"count":2,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3004\/revisions"}],"predecessor-version":[{"id":3008,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3004\/revisions\/3008"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3004"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3004"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3004"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}