{"id":78,"date":"2019-03-28T00:47:00","date_gmt":"2019-03-28T00:47:00","guid":{"rendered":"https:\/\/www.wangliguang.cn\/?p=78"},"modified":"2019-03-28T00:47:00","modified_gmt":"2019-03-28T00:47:00","slug":"ccfcsp%e6%95%b0%e6%8d%ae%e4%b8%ad%e5%bf%83","status":"publish","type":"post","link":"https:\/\/wangliguang.cn\/?p=78","title":{"rendered":"CCF CSP \u6570\u636e\u4e2d\u5fc3"},"content":{"rendered":"<h3>\u9898\u76ee<\/h3>\n<p>\u8bd5\u9898\u7f16\u53f7\uff1a    201812-4<br \/>\n\u8bd5\u9898\u540d\u79f0\uff1a   \u6570\u636e\u4e2d\u5fc3<br \/>\n\u65f6\u95f4\u9650\u5236\uff1a   1.0s<br \/>\n\u5185\u5b58\u9650\u5236\uff1a   512.0MB<br \/>\n\u95ee\u9898\u63cf\u8ff0\uff1a   <br \/>\n<img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20190328084249739.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5d2xnMTIz,size_16,color_FFFFFF,t_70\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><br \/>\n<img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20190328084234463.png\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><br \/>\n\u6837\u4f8b\u8f93\u5165<br \/>\n4<br \/>\n5<br \/>\n1<br \/>\n1 2 3<br \/>\n1 3 4<br \/>\n1 4 5<br \/>\n2 3 8<br \/>\n3 4 2<br \/>\n\u6837\u4f8b\u8f93\u51fa<br \/>\n4<br \/>\n\u6837\u4f8b\u8bf4\u660e<br \/>\n\u4e0b\u56fe\u662f\u6837\u4f8b\u8bf4\u660e\u3002<br \/>\n<img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20190328084223434.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcHB5d2xnMTIz,size_16,color_FFFFFF,t_70\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><br \/>\n<img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20190328084214480.png\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><\/p>\n<h3><a id=\"_29\"><\/a>\u5206\u6790<\/h3>\n<p>\u867d\u7136\u9898\u76ee\u8bf4\u7684\u5f88\u590d\u6742\uff0c\u4f46\u662f\u4ed4\u7ec6\u89c2\u5bdf\u6837\u4f8b\u540e\u53d1\u73b0\uff0c\u5176\u5b9e\u5c31\u662f\u4e00\u4e2a\u6700\u5c0f\u751f\u6210\u6811\u7684\u95ee\u9898\uff0c<strong>\u751a\u81f3\u90fd\u4e0d\u9700\u8981\u8003\u8651\u6839\u8282\u70b9\u5728\u4ec0\u4e48\u4f4d\u7f6e<\/strong>\uff0c\u56e0\u4e3a\u65e0\u8bba\u5728\u4ec0\u4e48\u4f4d\u7f6e\uff0c\u53ea\u8981\u628a\u6700\u5c0f\u751f\u6210\u6811\u6c42\u51fa\u6765\uff0c\u95ee\u9898\u5c31\u662f\u7b26\u5408\u9898\u76ee\u8981\u6c42\u7684\u3002<\/p>\n<h3><a id=\"_31\"><\/a>\u4ee3\u7801<\/h3>\n<h4><a id=\"1cmp_32\"><\/a>\u4ee3\u78011\uff1a\u5199cmp\u51fd\u6570\uff0c\u4e0d\u4f7f\u7528\u5bb9\u5668<\/h4>\n<pre><code class=\"prism language-cpp\"><span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span> <span class=\"token string\"><bits\/stdc++.h><\/span><\/span>\n<span class=\"token keyword\">using<\/span> <span class=\"token keyword\">namespace<\/span> std<span class=\"token punctuation\">;<\/span>\n<span class=\"token macro property\">#<span class=\"token directive keyword\">define<\/span> MAX 100001<\/span>\n<span class=\"token macro property\">#<span class=\"token directive keyword\">define<\/span> MAXN 500001<\/span>\n<span class=\"token keyword\">struct<\/span> Edge<span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> u<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> v<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> u1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> v1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> w1<span class=\"token punctuation\">)<\/span><span class=\"token operator\">:<\/span><span class=\"token function\">u<\/span><span class=\"token punctuation\">(<\/span>u1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> <span class=\"token function\">v<\/span><span class=\"token punctuation\">(<\/span>v1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> <span class=\"token function\">w<\/span><span class=\"token punctuation\">(<\/span>w1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span><span class=\"token punctuation\">}<\/span>\n<span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> pre<span class=\"token punctuation\">[<\/span>MAXN<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\nEdge edge<span class=\"token punctuation\">[<\/span>MAX<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">bool<\/span> <span class=\"token function\">cmp<\/span><span class=\"token punctuation\">(<\/span>Edge e1<span class=\"token punctuation\">,<\/span> Edge e2<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">return<\/span> e1<span class=\"token punctuation\">.<\/span>w <span class=\"token operator\"><<\/span> e2<span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">find<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> root<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> tmp<span class=\"token punctuation\">,<\/span> son<span class=\"token punctuation\">;<\/span>\n    son <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">while<\/span><span class=\"token punctuation\">(<\/span>root <span class=\"token operator\">!=<\/span> pre<span class=\"token punctuation\">[<\/span>root<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        root <span class=\"token operator\">=<\/span> pre<span class=\"token punctuation\">[<\/span>root<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">while<\/span><span class=\"token punctuation\">(<\/span>son <span class=\"token operator\">!=<\/span> root<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        tmp <span class=\"token operator\">=<\/span> pre<span class=\"token punctuation\">[<\/span>son<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n        pre<span class=\"token punctuation\">[<\/span>son<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n        son <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> root<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">bool<\/span> <span class=\"token function\">join<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> x<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> y<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> rootx <span class=\"token operator\">=<\/span> <span class=\"token function\">find<\/span><span class=\"token punctuation\">(<\/span>x<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> rooty <span class=\"token operator\">=<\/span> <span class=\"token function\">find<\/span><span class=\"token punctuation\">(<\/span>y<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>rootx <span class=\"token operator\">!=<\/span> rooty<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        pre<span class=\"token punctuation\">[<\/span>rootx<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> rooty<span class=\"token punctuation\">;<\/span>\n        <span class=\"token keyword\">return<\/span> <span class=\"token boolean\">true<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token boolean\">false<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">main<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> n <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> m <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> root <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> i <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> ans <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> num <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    cin <span class=\"token operator\">>><\/span> n <span class=\"token operator\">>><\/span> m <span class=\"token operator\">>><\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>n<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        pre<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> i<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>m<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        cin <span class=\"token operator\">>><\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>u <span class=\"token operator\">>><\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>v <span class=\"token operator\">>><\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">sort<\/span><span class=\"token punctuation\">(<\/span>edge<span class=\"token punctuation\">,<\/span> edge<span class=\"token operator\">+<\/span>m<span class=\"token punctuation\">,<\/span> cmp<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>m<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span><span class=\"token function\">join<\/span><span class=\"token punctuation\">(<\/span>edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>u<span class=\"token punctuation\">,<\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>v<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n            ans <span class=\"token operator\">=<\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n            num <span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span> <span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>\n            <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>num <span class=\"token operator\">==<\/span> n<span class=\"token operator\">-<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n                <span class=\"token keyword\">break<\/span><span class=\"token punctuation\">;<\/span>\n            <span class=\"token punctuation\">}<\/span>\n        <span class=\"token punctuation\">}<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    cout <span class=\"token operator\"><<<\/span> ans <span class=\"token operator\"><<<\/span> endl<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<\/code><\/pre>\n<h4><a id=\"2___103\"><\/a>\u4ee3\u78012\uff1a\u91cd\u8f7d < \u8fd0\u7b97\u7b26\uff0c\u4e0d\u4f7f\u7528\u5bb9\u5668<\/h4>\n<pre><code class=\"prism language-cpp\"><span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span> <span class=\"token string\"><bits\/stdc++.h><\/span><\/span>\n<span class=\"token keyword\">using<\/span> <span class=\"token keyword\">namespace<\/span> std<span class=\"token punctuation\">;<\/span>\n<span class=\"token macro property\">#<span class=\"token directive keyword\">define<\/span> MAX 100001<\/span>\n<span class=\"token macro property\">#<span class=\"token directive keyword\">define<\/span> MAXN 500001<\/span>\n<span class=\"token keyword\">struct<\/span> Edge<span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> u<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> v<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span><span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> u1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> v1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> w1<span class=\"token punctuation\">)<\/span><span class=\"token operator\">:<\/span><span class=\"token function\">u<\/span><span class=\"token punctuation\">(<\/span>u1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> <span class=\"token function\">v<\/span><span class=\"token punctuation\">(<\/span>v1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> <span class=\"token function\">w<\/span><span class=\"token punctuation\">(<\/span>w1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span><span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">bool<\/span> <span class=\"token keyword\">operator<\/span> <span class=\"token operator\"><<\/span> <span class=\"token punctuation\">(<\/span><span class=\"token keyword\">struct<\/span> Edge <span class=\"token operator\">&<\/span>e1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        <span class=\"token keyword\">return<\/span> <span class=\"token keyword\">this<\/span><span class=\"token operator\">-<\/span><span class=\"token operator\">><\/span>w <span class=\"token operator\"><<\/span> e1<span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n<span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> pre<span class=\"token punctuation\">[<\/span>MAXN<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\nEdge edge<span class=\"token punctuation\">[<\/span>MAX<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">find<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> root<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> tmp<span class=\"token punctuation\">,<\/span> son<span class=\"token punctuation\">;<\/span>\n    son <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">while<\/span><span class=\"token punctuation\">(<\/span>root <span class=\"token operator\">!=<\/span> pre<span class=\"token punctuation\">[<\/span>root<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        root <span class=\"token operator\">=<\/span> pre<span class=\"token punctuation\">[<\/span>root<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">while<\/span><span class=\"token punctuation\">(<\/span>son <span class=\"token operator\">!=<\/span> root<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        tmp <span class=\"token operator\">=<\/span> pre<span class=\"token punctuation\">[<\/span>son<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n        pre<span class=\"token punctuation\">[<\/span>son<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n        son <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> root<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">bool<\/span> <span class=\"token function\">join<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> x<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> y<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> rootx <span class=\"token operator\">=<\/span> <span class=\"token function\">find<\/span><span class=\"token punctuation\">(<\/span>x<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> rooty <span class=\"token operator\">=<\/span> <span class=\"token function\">find<\/span><span class=\"token punctuation\">(<\/span>y<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>rootx <span class=\"token operator\">!=<\/span> rooty<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        pre<span class=\"token punctuation\">[<\/span>rootx<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> rooty<span class=\"token punctuation\">;<\/span>\n        <span class=\"token keyword\">return<\/span> <span class=\"token boolean\">true<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token boolean\">false<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">main<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> n <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> m <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> root <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> i <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> ans <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> num <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    cin <span class=\"token operator\">>><\/span> n <span class=\"token operator\">>><\/span> m <span class=\"token operator\">>><\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>n<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        pre<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> i<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>m<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        cin <span class=\"token operator\">>><\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>u <span class=\"token operator\">>><\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>v <span class=\"token operator\">>><\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">sort<\/span><span class=\"token punctuation\">(<\/span>edge<span class=\"token punctuation\">,<\/span> edge<span class=\"token operator\">+<\/span>m<span class=\"token punctuation\">,<\/span> cmp<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>m<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span><span class=\"token function\">join<\/span><span class=\"token punctuation\">(<\/span>edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>u<span class=\"token punctuation\">,<\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>v<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n            ans <span class=\"token operator\">=<\/span> edge<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n            num <span class=\"token operator\">+<\/span><span class=\"token operator\">=<\/span> <span class=\"token number\">1<\/span><span class=\"token punctuation\">;<\/span>\n            <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>num <span class=\"token operator\">==<\/span> n<span class=\"token operator\">-<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n                <span class=\"token keyword\">break<\/span><span class=\"token punctuation\">;<\/span>\n            <span class=\"token punctuation\">}<\/span>\n        <span class=\"token punctuation\">}<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    cout <span class=\"token operator\"><<<\/span> ans <span class=\"token operator\"><<<\/span> endl<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<\/code><\/pre>\n<h4><a id=\"3___173\"><\/a>\u4ee3\u78013\uff1a\u91cd\u8f7d < \u8fd0\u7b97\u7b26\uff0c\u4f7f\u7528\u5bb9\u5668<\/h4>\n<pre><code class=\"prism language-cpp\"><span class=\"token macro property\">#<span class=\"token directive keyword\">include<\/span> <span class=\"token string\"><bits\/stdc++.h><\/span><\/span>\n<span class=\"token keyword\">using<\/span> <span class=\"token keyword\">namespace<\/span> std<span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">struct<\/span> Edge<span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> u<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> v<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span><span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> u1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> v1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> w1<span class=\"token punctuation\">)<\/span><span class=\"token operator\">:<\/span><span class=\"token function\">u<\/span><span class=\"token punctuation\">(<\/span>u1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> <span class=\"token function\">v<\/span><span class=\"token punctuation\">(<\/span>v1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> <span class=\"token function\">w<\/span><span class=\"token punctuation\">(<\/span>w1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span><span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">bool<\/span> <span class=\"token keyword\">operator<\/span> <span class=\"token operator\"><<\/span> <span class=\"token punctuation\">(<\/span><span class=\"token keyword\">struct<\/span> Edge <span class=\"token operator\">&<\/span>e1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        <span class=\"token keyword\">return<\/span> <span class=\"token keyword\">this<\/span><span class=\"token operator\">-<\/span><span class=\"token operator\">><\/span>w <span class=\"token operator\"><<\/span> e1<span class=\"token punctuation\">.<\/span>w<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n<span class=\"token punctuation\">}<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">const<\/span> <span class=\"token keyword\">int<\/span> maxn <span class=\"token operator\">=<\/span> <span class=\"token number\">500001<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">const<\/span> <span class=\"token keyword\">int<\/span> maxm <span class=\"token operator\">=<\/span> <span class=\"token number\">100001<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> pre<span class=\"token punctuation\">[<\/span>maxn<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\nvector<span class=\"token operator\"><<\/span>Edge<span class=\"token operator\">><\/span> edge<span class=\"token punctuation\">;<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">findx<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> root<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> son<span class=\"token punctuation\">,<\/span> tmp<span class=\"token punctuation\">;<\/span>\n    son <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">while<\/span><span class=\"token punctuation\">(<\/span>root <span class=\"token operator\">!=<\/span> pre<span class=\"token punctuation\">[<\/span>root<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        root  <span class=\"token operator\">=<\/span> pre<span class=\"token punctuation\">[<\/span>root<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">while<\/span><span class=\"token punctuation\">(<\/span>son <span class=\"token operator\">!=<\/span> root<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        tmp <span class=\"token operator\">=<\/span> pre<span class=\"token punctuation\">[<\/span>son<span class=\"token punctuation\">]<\/span><span class=\"token punctuation\">;<\/span>\n        pre<span class=\"token punctuation\">[<\/span>son<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> root<span class=\"token punctuation\">;<\/span>\n        son <span class=\"token operator\">=<\/span> tmp<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> root<span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">join<\/span><span class=\"token punctuation\">(<\/span><span class=\"token keyword\">int<\/span> root1<span class=\"token punctuation\">,<\/span> <span class=\"token keyword\">int<\/span> root2<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> x <span class=\"token operator\">=<\/span> <span class=\"token function\">findx<\/span><span class=\"token punctuation\">(<\/span>root1<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> y <span class=\"token operator\">=<\/span> <span class=\"token function\">findx<\/span><span class=\"token punctuation\">(<\/span>root2<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>x <span class=\"token operator\">!=<\/span> y<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        pre<span class=\"token punctuation\">[<\/span>x<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> y<span class=\"token punctuation\">;<\/span>\n        <span class=\"token keyword\">return<\/span> <span class=\"token boolean\">true<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token boolean\">false<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<span class=\"token keyword\">int<\/span> <span class=\"token function\">main<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n    <span class=\"token keyword\">int<\/span> n <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> m <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> i <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> ans <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> num <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">,<\/span> root <span class=\"token operator\">=<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">int<\/span> tmp1<span class=\"token punctuation\">,<\/span> tmp2<span class=\"token punctuation\">,<\/span> tmp3<span class=\"token punctuation\">;<\/span>\n    cin <span class=\"token operator\">>><\/span> n <span class=\"token operator\">>><\/span> m <span class=\"token operator\">>><\/span> root<span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>m<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        cin <span class=\"token operator\">>><\/span> tmp1 <span class=\"token operator\">>><\/span> tmp2 <span class=\"token operator\">>><\/span> tmp3<span class=\"token punctuation\">;<\/span>\n        edge<span class=\"token punctuation\">.<\/span><span class=\"token function\">push_back<\/span><span class=\"token punctuation\">(<\/span><span class=\"token function\">Edge<\/span><span class=\"token punctuation\">(<\/span>tmp1<span class=\"token punctuation\">,<\/span> tmp2<span class=\"token punctuation\">,<\/span> tmp3<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>i<span class=\"token operator\">=<\/span><span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span> i<span class=\"token operator\"><<\/span>n<span class=\"token punctuation\">;<\/span> i<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        pre<span class=\"token punctuation\">[<\/span>i<span class=\"token punctuation\">]<\/span> <span class=\"token operator\">=<\/span> i<span class=\"token punctuation\">;<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token function\">sort<\/span><span class=\"token punctuation\">(<\/span>edge<span class=\"token punctuation\">.<\/span><span class=\"token function\">begin<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">,<\/span> edge<span class=\"token punctuation\">.<\/span><span class=\"token function\">end<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span>\n    <span class=\"token keyword\">for<\/span><span class=\"token punctuation\">(<\/span>vector<span class=\"token operator\"><<\/span>Edge<span class=\"token operator\">><\/span><span class=\"token operator\">::<\/span>iterator it <span class=\"token operator\">=<\/span> edge<span class=\"token punctuation\">.<\/span><span class=\"token function\">begin<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span> it <span class=\"token operator\">!=<\/span> edge<span class=\"token punctuation\">.<\/span><span class=\"token function\">end<\/span><span class=\"token punctuation\">(<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">;<\/span> it<span class=\"token operator\">++<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n        <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span><span class=\"token function\">join<\/span><span class=\"token punctuation\">(<\/span>it<span class=\"token operator\">-<\/span><span class=\"token operator\">><\/span>u<span class=\"token punctuation\">,<\/span> it<span class=\"token operator\">-<\/span><span class=\"token operator\">><\/span>v<span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n            ans <span class=\"token operator\">=<\/span> it<span class=\"token operator\">-<\/span><span class=\"token operator\">><\/span>w<span class=\"token punctuation\">;<\/span>\n            num<span class=\"token operator\">++<\/span><span class=\"token punctuation\">;<\/span>\n            <span class=\"token keyword\">if<\/span><span class=\"token punctuation\">(<\/span>num <span class=\"token operator\">==<\/span> n<span class=\"token operator\">-<\/span><span class=\"token number\">1<\/span><span class=\"token punctuation\">)<\/span><span class=\"token punctuation\">{<\/span>\n                cout <span class=\"token operator\"><<<\/span> ans<span class=\"token punctuation\">;<\/span>\n                <span class=\"token keyword\">break<\/span><span class=\"token punctuation\">;<\/span>\n            <span class=\"token punctuation\">}<\/span>\n        <span class=\"token punctuation\">}<\/span>\n    <span class=\"token punctuation\">}<\/span>\n    <span class=\"token keyword\">return<\/span> <span class=\"token number\">0<\/span><span class=\"token punctuation\">;<\/span>\n<span class=\"token punctuation\">}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee \u8bd5\u9898\u7f16\u53f7\uff1a 201812-4 \u8bd5\u9898\u540d\u79f0\uff1a \u6570\u636e\u4e2d\u5fc3 \u65f6\u95f4\u9650\u5236\uff1a 1.0s \u5185\u5b58\u9650\u5236\uff1a 512.0MB \u95ee&hellip; <a href=\"https:\/\/wangliguang.cn\/?p=78\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb <span class=\"screen-reader-text\">CCF CSP \u6570\u636e\u4e2d\u5fc3<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[21,22],"tags":[43,44],"class_list":["post-78","post","type-post","status-publish","format-standard","hentry","category-21","category-22","tag-43","tag-44"],"_links":{"self":[{"href":"https:\/\/wangliguang.cn\/index.php?rest_route=\/wp\/v2\/posts\/78","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wangliguang.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wangliguang.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wangliguang.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wangliguang.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=78"}],"version-history":[{"count":0,"href":"https:\/\/wangliguang.cn\/index.php?rest_route=\/wp\/v2\/posts\/78\/revisions"}],"wp:attachment":[{"href":"https:\/\/wangliguang.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=78"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wangliguang.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=78"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wangliguang.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=78"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}