{"published":"2020-05-26 22:16:15","type":"rich","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbouzuya.hatenablog.com%2Fentry%2F2020%2F05%2F26%2F221615\" title=\"past201912_l \u3092\u89e3\u3044\u305f - bouzuya.hatenablog.com\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","image_url":null,"author_url":"https://blog.hatena.ne.jp/bouzuya/","categories":[],"version":"1.0","description":"PAST201912 L \u30b0\u30e9\u30c7\u30fc\u30b7\u30e7\u30f3 Gradation \u3092\u89e3\u3044\u305f\u3002\u81ea\u529b\u3067\u306f\u89e3\u3051\u306a\u304b\u3063\u305f\u3002 \u4f7f\u7528\u3059\u308b\u5c0f\u3055\u3044\u5854\u306e\u7d44\u307f\u5408\u308f\u305b\u3092 bit \u5168\u63a2\u7d22\u3067\u5217\u6319\u3059\u308b\u3002\u5927\u304d\u3044\u5854\u3068\u4f7f\u3046\u5c0f\u3055\u3044\u5854\u306b\u5bfe\u3057\u3066 MST: Minimum Spanning Tree \u6700\u5c0f\u5168\u57df\u6728 (\u306e\u8fba\u306e\u30b3\u30b9\u30c8\u306e\u5408\u8a08) \u3092\u6c42\u3081\u305f\u3002 MST \u306f\u30af\u30e9\u30b9\u30ab\u30eb\u6cd5\u3067\u6c42\u3081\u305f\u3002 \u30af\u30e9\u30b9\u30ab\u30eb\u6cd5\u306f\u8fba\u3092\u30b3\u30b9\u30c8\u9806\u306b\u4e26\u3079\u3066 UnionFind \u3067\u9023\u7d50\u3057\u3066\u3044\u304f\u3002\u305d\u306e\u8fba\u304c\u65b0\u305f\u306b\u9023\u7d50\u3055\u308c\u308b\u9802\u70b9\u3078\u306e\u3082\u306e\u306a\u3089\u6700\u5c0f\u5168\u57df\u6728 (\u30b3\u30b9\u30c8\u306e\u5408\u8a08) \u306b\u52a0\u3048\u308b\u3002\u554f\u984c\u3068\u306f\u9055\u3046\u304c\u30a4\u30e1\u30fc\u30b8\u306f \u2193\u3002 // (cost, u, v) let mut e: Vec<(i64, usize, usi\u2026","title":"past201912_l \u3092\u89e3\u3044\u305f","provider_name":"Hatena Blog","blog_title":"bouzuya.hatenablog.com","height":"190","blog_url":"https://bouzuya.hatenablog.com/","provider_url":"https://hatena.blog","url":"https://bouzuya.hatenablog.com/entry/2020/05/26/221615","author_name":"bouzuya","width":"100%"}