{"id":27,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-18\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-18","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-18\/","title":{"rendered":"2020-08-18"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2548&pid=4<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

\u5728\u4e00\u7247\u6816\u606f\u5730\u4e0a\u6709N\u68f5\u6811\uff0c\u6bcf\u68f5\u6811\u4e0b\u4f4f\u7740\u4e00\u53ea\u5154\u5b50\uff0c\u6709M\u6761\u8def\u5f84\u8fde\u63a5\u8fd9\u4e9b\u6811\u3002\u66f4\u7279\u6b8a\u5730\u662f\uff0c\u53ea\u6709\u4e00\u68f5\u6811\u67093\u6761\u6216\u66f4\u591a\u7684\u8def\u5f84\u4e0e\u5b83\u76f8\u8fde\uff0c\u5176\u5b83\u7684\u6811\u53ea\u67091\u6761\u62162\u6761\u8def\u5f84\u4e0e\u5176\u76f8\u8fde\u3002\u6362\u53e5\u8bdd\u8bb2\uff0c\u8fd9\u4e9b\u6811\u548c\u6811\u4e4b\u95f4\u7684\u8def\u5f84\u6784\u6210\u4e00\u5f20N\u4e2a\u70b9\u3001M\u6761\u8fb9\u7684\u65e0\u5411\u8fde\u901a\u56fe\uff0c\u800c\u5ea6\u6570\u5927\u4e8e2\u7684\u70b9\u81f3\u591a\u67091\u4e2a\u3002
\u8fd1\u5e74\u4ee5\u6765\uff0c\u6816\u606f\u5730\u9891\u7e41\u6536\u5230\u4eba\u7c7b\u7684\u4fb5\u6270\u3002\u5154\u5b50\u4eec\u8054\u5408\u8d77\u6765\u53ec\u5f00\u4e86\u4e00\u573a\u4f1a\u8bae\uff0c\u51b3\u5b9a\u5728\u5176\u4e2dK\u68f5\u6811\u4e0a\u5efa\u9020\u6811\u6d1e\u3002\u5f53\u5371\u9669\u6765\u4e34\u65f6\uff0c\u6bcf\u53ea\u5154\u5b50\u5747\u4f1a\u540c\u65f6\u524d\u5f80\u8ddd\u79bb\u5b83\u6700\u8fd1\u7684\u6811\u6d1e\u8eb2\u907f\uff0c\u8def\u7a0b\u4e2d\u82b1\u8d39\u7684\u65f6\u95f4\u5728\u6570\u503c\u4e0a\u7b49\u4e8e\u8ddd\u79bb\u3002\u4e3a\u4e86\u5728\u6700\u77ed\u7684\u65f6\u95f4\u5185\u8ba9\u6240\u6709\u5154\u5b50\u8131\u79bb\u5371\u9669\uff0c\u8bf7\u4f60\u5b89\u6392\u4e00\u79cd\u5efa\u9020\u6811\u6d1e\u7684\u65b9\u5f0f\uff0c\u4f7f\u6700\u540e\u4e00\u53ea\u5230\u8fbe\u6811\u6d1e\u7684\u5154\u5b50\u6240\u82b1\u8d39\u7684\u65f6\u95f4\u5c3d\u91cf\u5c11\u3002<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

\u7b2c\u4e00\u884c\u67093\u4e2a\u6574\u6570N\uff0cM\uff0cK\uff0c\u5206\u522b\u8868\u793a\u6811\uff08\u5154\u5b50\uff09\u7684\u4e2a\u6570\u3001\u8def\u5f84\u6570\u3001\u8ba1\u5212\u5efa\u9020\u7684\u6811\u6d1e\u6570\u3002
\u63a5\u4e0b\u6765M\u884c\u6bcf\u884c\u4e09\u4e2a\u6574\u6570x,y\uff0c\u8868\u793a\u7b2cx\u68f5\u6811\u548c\u7b2cy\u68f5\u6811\u4e4b\u95f4\u6709\u4e00\u6761\u8def\u5f84\u76f8\u8fde\u30021<=x,y<=N\uff0cx\u2260y\uff0c\u4efb\u610f\u4e24\u68f5\u6811\u4e4b\u95f4\u81f3\u591a\u53ea\u67091\u6761\u8def\u5f84\u3002<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u5728\u6700\u4f18\u65b9\u6848\u4e0b\uff0c\u6700\u540e\u4e00\u53ea\u5230\u8fbe\u6811\u6d1e\u7684\u5154\u5b50\u6240\u82b1\u8d39\u7684\u65f6\u95f4\u3002<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
5 5 2\n1 2\n2 3\n3 1\n1 4\n4 5\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
1\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h5>\n
\u5bf9\u4e8e20%\u7684\u6570\u636e\uff0c1\u2009\u2264\u2009 n\u2009\u2264\u200910\u3002
 \u5bf9\u4e8e\u53e6\u591630%\u7684\u6570\u636e\uff0c\u6bcf\u68f5\u6811\u81f3\u591a\u4e0e2\u6761\u8def\u5f84\u76f8\u8fde\u3002
 \u5bf9\u4e8e\u53e6\u591630%\u7684\u6570\u636e\uff0c\u4fdd\u8bc1\u5b58\u5728\u4e00\u79cd\u6700\u4f18\u89e3\uff0c\u4f7f\u4e0e3\u6761\u6216\u66f4\u591a\u8def\u5f84\u76f8\u8fde\u7684\u6811\u4e0a\u4e00\u5b9a\u5efa\u9020\u4e86\u6811\u6d1e\u3002
 \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c1\u2009\u2264\u2009n\u2009\u2264\u20092000\uff0cn-1<=m<=n*(n-1)\/2\u3002<\/p>\n
<\/a>\u89e3\u6790<\/h5>\n
\u56fe\u8bba+\u4e8c\u5206\u67e5\u627e
 \u6ce8\uff1a\u672c\u9898\u7f3a\u4e4f\u6d4b\u8bd5\u7528\u4f8b\uff0c\u53ef\u80fd\u4f1a\u6709bug\uff0c\u5efa\u8bae\u53c2\u7167\u535a\u5ba2\uff1a
 https:\/\/www.cnblogs.com\/Shawn7xc\/p\/7771441.html<\/a>
 https:\/\/www.cnblogs.com\/candy99\/p\/6003565.html<\/a><\/p>\n
#include<\/span><\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> to;<\/span>\n    int<\/span> next;<\/span>\n}<\/span>;<\/span>\nint<\/span> n,<\/span>m,<\/span>x,<\/span>y,<\/span>k;<\/span>\nint<\/span> head[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> vis[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> first[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> e[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nnode a[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> root=<\/span>0<\/span>;<\/span>\nint<\/span> cnt=<\/span>0<\/span>;<\/span>\nint<\/span> deep=<\/span>0<\/span>;<\/span>\nint<\/span> dfs<\/span>(<\/span>int<\/span> n,<\/span>int<\/span> len)<\/span>\n{<\/span>\n    deep+<\/span>=<\/span>1<\/span>;<\/span>\n    vis[<\/span>n]<\/span>=<\/span>1<\/span>;<\/span>\n    if<\/span>(<\/span>len==<\/span>0<\/span>)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>head[<\/span>n]<\/span>;<\/span>i;<\/span>i=<\/span>a[<\/span>i]<\/span>.<\/span>next)<\/span>\n    {<\/span>\n        int<\/span> w=<\/span>a[<\/span>i]<\/span>.<\/span>to;<\/span>\n        if<\/span>(<\/span>!<\/span>vis[<\/span>w]<\/span>)<\/span>\n        {<\/span>\n            dfs<\/span>(<\/span>w,<\/span>len-<\/span>1<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> add<\/span>(<\/span>int<\/span> x,<\/span>int<\/span> y)<\/span>\n{<\/span>\n    a[<\/span>++<\/span>cnt]<\/span>.<\/span>to=<\/span>y;<\/span>\n    a[<\/span>cnt]<\/span>.<\/span>next=<\/span>head[<\/span>x]<\/span>;<\/span>\n    head[<\/span>x]<\/span>=<\/span>cnt;<\/span>\n}<\/span>\nint<\/span> check<\/span>(<\/span>int<\/span> x)<\/span>\n{<\/span>\n    memset<\/span>(<\/span>vis,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>vis)<\/span>)<\/span>;<\/span>\n    dfs<\/span>(<\/span>root,<\/span>x)<\/span>;<\/span>\n    memcpy<\/span>(<\/span>first,<\/span>vis,<\/span>sizeof<\/span>(<\/span>vis)<\/span>)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>first[<\/span>i]<\/span>)<\/span>\n        {<\/span>\n            int<\/span> out=<\/span>1<\/span>;<\/span>\n            memset<\/span>(<\/span>vis,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>vis)<\/span>)<\/span>;<\/span>\n            dfs<\/span>(<\/span>i,<\/span>x)<\/span>;<\/span>\n            for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>n;<\/span>j++<\/span>)<\/span>\n            {<\/span>\n                if<\/span>(<\/span>!<\/span>vis[<\/span>j]<\/span>)<\/span>\n                {<\/span>\n                    deep=<\/span>0<\/span>;<\/span>\n                    dfs<\/span>(<\/span>j,<\/span>n)<\/span>;<\/span>\n                    out+<\/span>=<\/span>(<\/span>deep+<\/span>2<\/span>*<\/span>x)<\/span>\/<\/span>(<\/span>2<\/span>*<\/span>x+<\/span>1<\/span>)<\/span>;<\/span>\n                }<\/span>\n            }<\/span>\n            if<\/span>(<\/span>out<=<\/span>k)<\/span>\n                return<\/span> 1<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%d%d%%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m,<\/span>&<\/span>k)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>x,<\/span>&<\/span>y)<\/span>;<\/span>\n        add<\/span>(<\/span>x,<\/span>y)<\/span>;<\/span>\n        add<\/span>(<\/span>y,<\/span>x)<\/span>;<\/span>\n        e[<\/span>x]<\/span>++<\/span>;<\/span>\n        e[<\/span>y]<\/span>++<\/span>;<\/span>\n    }<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>e[<\/span>i]<\/span>><\/span>2<\/span>)<\/span>\n        {<\/span>\n            root=<\/span>i;<\/span>\n            break<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    if<\/span>(<\/span>!<\/span>root)<\/span>\n    {<\/span>\n        cout<<<\/span>(<\/span>n+<\/span>k-<\/span>1<\/span>)<\/span>\/<\/span>k\/<\/span>2<\/span><<<\/span>endl;<\/span>\n        exit<\/span>(<\/span>0<\/span>)<\/span>;<\/span>\n    }<\/span>\n    int<\/span> l=<\/span>1<\/span>,<\/span>r=<\/span>n+<\/span>1<\/span>;<\/span>\n    while<\/span>(<\/span>l<<\/span>r)<\/span>\n    {<\/span>\n        int<\/span> mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>\n        if<\/span>(<\/span>check<\/span>(<\/span>mid)<\/span>)<\/span>\n        {<\/span>\n            l=<\/span>mid+<\/span>1<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            r=<\/span>mid;<\/span>\n        }<\/span>\n    }<\/span>\n    cout<<<\/span>l<<<\/span>endl;<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-27","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/27","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=27"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/27\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=27"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=27"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=27"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}