{"id":1034,"date":"2014-10-16T01:40:05","date_gmt":"2014-10-15T17:40:05","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1034"},"modified":"2014-10-16T01:40:27","modified_gmt":"2014-10-15T17:40:27","slug":"ioi-2008","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/ioi-2008\/","title":{"rendered":"IOI 2008"},"content":{"rendered":"<p><a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1791\">http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1791<\/a><br \/>\n<a href=\"http:\/\/www.spoj.com\/OI\/problems\/ISLAND\/\">http:\/\/www.spoj.com\/OI\/problems\/ISLAND\/<\/a><\/p>\n<p><!--more--><\/p>\n<h2>D2T1  Islands<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6811\u52a0\u4e00\u6761\u8fb9\u3002\u3002\u6c42\u8fd9\u4e2a\u56fe\u7684\u6700\u957f\u94fe\u3002<\/p>\n<h3>Analysis: <\/h3>\n<blockquote class=\"wp-embedded-content\" data-secret=\"qbdKxvOpOC\"><p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-beta-round-88\/\">Codeforces Beta Round #88<\/a><\/p><\/blockquote>\n<p><iframe loading=\"lazy\" class=\"wp-embedded-content\" sandbox=\"allow-scripts\" security=\"restricted\" style=\"position: absolute; clip: rect(1px, 1px, 1px, 1px);\" title=\"&#8220;Codeforces Beta Round #88&#8221; &#8212; \u67d0\u5c9b\" src=\"https:\/\/www.shuizilong.com\/house\/archives\/codeforces-beta-round-88\/embed\/#?secret=VNFBjCHG3e#?secret=qbdKxvOpOC\" data-secret=\"qbdKxvOpOC\" width=\"500\" height=\"282\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\"><\/iframe><\/p>\n<p>\u4e00\u68f5\u6811\u52a0\u4e00\u6761\u8fb9\u5c31\u662f\u4f1a\u6709\u4e00\u4e2a\u73af\u3002\u3002\u8ba8\u8bba\u6700\u957f\u94fe\u3002\u3002<\/p>\n<p>\u4e0d\u5728\u73af\u4e0a\u3002\u3002\u90a3\u4e48\u89c4\u7ea6\u5230\u6811\u4e0a\u6700\u957f\u94fe\u3002\u3002<br \/>\n\u5728\u73af\u4e0a\u3002\u3002<\/p>\n<p>\u90a3\u4e48\u8bbe d[i] \u8868\u793a\u73af\u4e0a\u67d0\u4e2a\u70b9\u5411\u4e0b\u6240\u80fd\u5230\u8fbe\u7684\u6700\u8fdc\u70b9\u3002<br \/>\n\u3002\u3002 s[i] \u8868\u793a\u73af\u4e0a\u7b2c 0 \u4e2a\u7ed3\u70b9\uff0c\u6cbf\u7740\u6b63\u65b9\u5411\u5230\u7b2c i \u4e2a\u7ed3\u70b9\u4e4b\u95f4\u7684\u8ddd\u79bb\u3002\u3002\u3002<br \/>\n\u3002\u3002dist(i, j) \u8868\u793a\u73af\u4e0a\u4e24\u4e2a\u70b9\u7684\u6700\u957f\u8def\u5f84\u3002\u3002\u8ba8\u8bba\u65b9\u5411\u3002\u3002<br \/>\n\u3002\u3002\u6709 dist(i, j) = max(s[i] &#8211; s[j], ss &#8211; (s[i] &#8211; s[j))<\/p>\n<p>\u3002\u3002ss \u8868\u793a\u6574\u4e2a\u73af\u7684\u957f\u5ea6\u3002\u3002<\/p>\n<p>\u7b54\u6848\u5c31\u662f max{ d[i] + d[j] + dist(i, j)  | j < i }\n\u628a\u4e0a\u5f0f\u62c6\u5f00\u3002\u3002\n\n\u5c31\u662f\u6bcf\u6b21\u3002\u3002\u627e\u3002\u3002\n\nmax{\n     d[i] + s[i] + max(d[j] - s[j]),\n     ss + d[i]-s[i] +max(d[j] + s[j]);\n}\n\n\u7136\u540e O(n) \u626b\u63cf\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u3002\n\n\n[cpp]\n\n\/\/}\/* .................................................................................................................................. *\/\n\nconst int N = int(1e6) + 9, M = 2*N;\n\nLL dd[N], d[N], s[N]; int c[N]; int nn;\nint Q[N], cz, op, uu;\n\nint hd[N], prd[M], suc[M], to[M], ww[N];\nint n;\n\n#define aa to[i^1]\n#define bb to[i]\n#define w ww[i\/2]\n\n    inline void del(int i){\n        if (hd[aa] == i) prd[hd[aa] = suc[i]] = 0;\n        else suc[prd[suc[i]] = prd[i]] = suc[i];\n    }\n\n    inline void dell(int i){\n        del(i), del(i^1);\n    }\n\nint vis[N]; bool st[N];\n#define v (bb)\n\nbool dfs(int u, int p = -1){ \/\/ Find_Circle\n    vis[u] = 1; REP_G(i, u) if (i != p){\n        if (vis[v]) st[v] = 1;\n        if (vis[v] || dfs(v, i^1)){\n            c[nn] = v, s[nn+1] = s[nn] + w, ++nn, dell(i);\n            return !st[u];\n        }\n    }\n    return 0;\n}\n\nLL f(int x){\n\n    nn = 0, dfs(x); LL z = 0; REP(ii, nn){\n\n        int s = c[ii], ss = s; dd[ii] = 0;\n\n        cz = 0, op = 1; Q[0] = s; d[s] = 0; vis[s] = 2;\n\n        while (cz &lt; op){\n            int u = Q[cz++]; REP_G(i, u) if (vis[v] != 2){\n                d[v] = d[u] + w;\n                vis[v] = 2, Q[op++] = v;\n\n                if (d[v] &gt; dd[ii]){\n                    dd[ii] = d[v];\n                    ss = v;\n                }\n            }\n        }\n\n        cz = 0, op = 1; Q[0] = ss, d[ss] = 0; vis[ss] = 3;\n\n        while (cz &lt; op){\n            int u = Q[cz++]; REP_G(i, u) if (vis[v] != 3){\n                d[v] = d[u] + w;\n                vis[v] = 3, Q[op++] = v;\n\n                checkMax(z, d[v]);\n            }\n        }\n    }\n\n#define d dd\n    LL ss=s[nn],pre1=d[0]-s[0],pre2=d[0]+s[0]; FOR(i,1,nn){\n        checkMax(z, d[i]+max(s[i]+pre1,ss-s[i]+pre2));\n        checkMax(pre1, d[i]-s[i]), checkMax(pre2, d[i]+s[i]);\n    }\n    return z;\n}\n\nint main(){\n\n#ifndef ONLINE_JUDGE\n    freopen(&quot;isl19g.in&quot;, &quot;r&quot;, stdin);\n    freopen(&quot;isl5.txt&quot;, &quot;w&quot;, stdout);\n#endif\n\n    RD(n); for (int i=2,a=1;i&lt;=n&lt;&lt;1;++a){\n        aa = a, RD(bb, w);\n        prd[hd[aa]] = i, suc[i] = hd[aa], hd[aa] = i++;\n        prd[hd[aa]] = i, suc[i] = hd[aa], hd[aa] = i++;\n    }\n\n    LL z = 0; REP_1(i, n) if (!vis[i]) z += f(i); OT(z);\n}\n[\/cpp]\n\n\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1791 http:\/\/www.spoj.com\/OI\/problems\/ISLAND\/<\/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-1034","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-gG","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1034","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=1034"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1034\/revisions"}],"predecessor-version":[{"id":1035,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1034\/revisions\/1035"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1034"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1034"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1034"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}