Domovská stránka Prehľadávať Pomoc
Registrovať Prihlásiť sa
schtonn
/
public
1
1
Fork 0
Súbory Issues 0 Pull requesty 0 Wiki
Strom: 4ce897a68f
Branche Tagy
public
/
2020
/
03
/
01
/
min-span-tree
/
index.html

index.html 26 KB
História Raw

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282 
  1. <!DOCTYPE html>
    2. 

  2. <html>
    3. 

  3. <head>
    4. 

  4.   <meta charset="utf-8">
    5. 

  5.   
    6. 

  6. 

  7.   
    8. 

  8.   <title>最小生成树 | Schtonn&#39;s Blog</title>
    9. 

  9.   <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    10. 

  10.   <meta name="description" content="前置知识
 存图方式（邻接表，邻接矩阵），并查集。 不会的快进入链接学习吧！
 引入
 生成树，就是从一个图中选中\(n-1\)条边，使得这些边构成一棵树，并包含图中的所有节点。 最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。">
    11. 

  11. <meta property="og:type" content="article">
    12. 

  12. <meta property="og:title" content="最小生成树">
    13. 

  13. <meta property="og:url" content="http://yoursite.com/2020/03/01/min-span-tree/index.html">
    14. 

  14. <meta property="og:site_name" content="Schtonn&#39;s Blog">
    15. 

  15. <meta property="og:description" content="前置知识
 存图方式（邻接表，邻接矩阵），并查集。 不会的快进入链接学习吧！
 引入
 生成树，就是从一个图中选中\(n-1\)条边，使得这些边构成一棵树，并包含图中的所有节点。 最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。">
    16. 

  16. <meta property="og:locale" content="en_US">
    17. 

  17. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103203601629.png">
    18. 

  18. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103204749157.png">
    19. 

  19. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103205741495.png">
    20. 

  20. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103210306831.png">
    21. 

  21. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103210445854.png">
    22. 

  22. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103210621487.png">
    23. 

  23. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103210727778.png">
    24. 

  24. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103215213917.png">
    25. 

  25. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103215304212.png">
    26. 

  26. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103215356204.png">
    27. 

  27. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103215507942.png">
    28. 

  28. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200103215600881.png">
    29. 

  29. <meta property="article:published_time" content="2020-03-01T14:45:44.000Z">
    30. 

  30. <meta property="article:modified_time" content="2020-03-03T12:40:44.827Z">
    31. 

  31. <meta property="article:author" content="Schtonn">
    32. 

  32. <meta property="article:tag" content="graph">
    33. 

  33. <meta name="twitter:card" content="summary">
    34. 

  34. <meta name="twitter:image" content="https://img-blog.csdnimg.cn/20200103203601629.png">
    35. 

  35.   
    36. 

  36.     <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
    37. 

  37.   
    38. 

  38.   
    39. 

  39.     <link rel="icon" href="/favicon.png">
    40. 

  40.   
    41. 

  41.   
    42. 

  42.     <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
    43. 

  43.   
    44. 

  44.   
    45. 

  45. <link rel="stylesheet" href="/css/style.css">
    46. 

  46. 

  47. <meta name="generator" content="Hexo 4.2.0"></head>
    48. 

  48. 

  49. <body>
    50. 

  50.   <div id="container">
    51. 

  51.     <div id="wrap">
    52. 

  52.       <header id="header">
    53. 

  53.   <div id="banner"></div>
    54. 

  54.   <div id="header-outer" class="outer">
    55. 

  55.     <div id="header-title" class="inner">
    56. 

  56.       <h1 id="logo-wrap">
    57. 

  57.         <a href="/" id="logo">Schtonn&#39;s Blog</a>
    58. 

  58.       </h1>
    59. 

  59.       
    60. 

  60.         <h2 id="subtitle-wrap">
    61. 

  61.           <a href="/" id="subtitle">Schtonn&#39;s blog</a>
    62. 

  62.         </h2>
    63. 

  63.       
    64. 

  64.     </div>
    65. 

  65.     <div id="header-inner" class="inner">
    66. 

  66.       <nav id="main-nav">
    67. 

  67.         <a id="main-nav-toggle" class="nav-icon"></a>
    68. 

  68.         
    69. 

  69.           <a class="main-nav-link" href="/">Home</a>
    70. 

  70.         
    71. 

  71.           <a class="main-nav-link" href="/archives">Archives</a>
    72. 

  72.         
    73. 

  73.       </nav>
    74. 

  74.       <nav id="sub-nav">
    75. 

  75.         
    76. 

  76.           <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
    77. 

  77.         
    78. 

  78.         <a id="nav-search-btn" class="nav-icon" title="Search"></a>
    79. 

  79.       </nav>
    80. 

  80.       <div id="search-form-wrap">
    81. 

  81.         <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
    82. 

  82.       </div>
    83. 

  83.     </div>
    84. 

  84.   </div>
    85. 

  85. </header>
    86. 

  86.       <div class="outer">
    87. 

  87.         <section id="main"><article id="post-min-span-tree" class="article article-type-post" itemscope itemprop="blogPost">
    88. 

  88.   <div class="article-meta">
    89. 

  89.     <a href="/2020/03/01/min-span-tree/" class="article-date">
    90. 

  90.   <time datetime="2020-03-01T14:45:44.000Z" itemprop="datePublished">2020-Mar-01</time>
    91. 

  91. </a>
    92. 

  92.     
    93. 

  93.   </div>
    94. 

  94.   <div class="article-inner">
    95. 

  95.     
    96. 

  96.     
    97. 

  97.       <header class="article-header">
    98. 

  98.         
    99. 

  99.   
    100. 

  100.     <h1 class="article-title" itemprop="name">
    101. 

  101.       最小生成树
    102. 

  102.     </h1>
    103. 

  103.   
    104. 

  104. 

  105.       </header>
    106. 

  106.     
    107. 

  107.     <div class="article-entry" itemprop="articleBody">
    108. 

  108.       
    109. 

  109.         <h3 id="前置知识">前置知识</h3>
    110. 

  110. <p>存图方式（<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了，没有一个打得过的">邻接矩阵</a>），<a href="https://schtonn.github.io/2020/03/01/union-find" target="_blank" rel="noopener">并查集</a>。 不会的快进入链接学习吧！</p>
    111. 

  111. <h3 id="引入">引入</h3>
    112. 

  112. <p>生成树，就是从一个图中选中<span class="math inline">\(n-1\)</span>条边，使得这些边构成一棵树，并包含图中的所有节点。 最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。 <a id="more"></a></p>
    113. 

  113. <h3 id="生成方式一prim">生成方式一：prim</h3>
    114. 

  114. <p>这种方法有点类似<a href="http://baidu.physton.com/?q=dijkstra" target="_blank" rel="noopener" title="这都不会？">Dijstra</a>，就是每次从所有<span class="math inline">\(vis\)</span>过的点遍历能达到的边，从其中选择一条最小的，加入生成树。</p>
    115. 

  115. <hr />
    116. 

  116. <p>假设我们有这么一张图： <a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103203601629.png" alt="弟弟" /></a></p>
    117. 

  117. <p>就从0号点开始吧： <a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103204749157.png" alt="在这里插入图片描述" /></a></p>
    118. 

  118. <p>找到从<span class="math inline">\(0\)</span>出发的最小的边：<span class="math inline">\([0,2]\)</span>,边权为<span class="math inline">\(3\)</span>，那么对<span class="math inline">\(2\)</span>号点进行标记。 <a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103205741495.png" /></a></p>
    119. 

  119. <p>然后从<span class="math inline">\(0\)</span>号和<span class="math inline">\(2\)</span>号节点继续找，发现最小的是<span class="math inline">\([2,4]\)</span>边，那么就标记<span class="math inline">\(4\)</span>号节点。 <a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103210306831.png" alt="在这里插入图片描述" /></a></p>
    120. 

  120. <p>然后是<span class="math inline">\([4,1]\)</span>，<span class="math inline">\(1\)</span>号。 <a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103210445854.png" alt="在这里插入图片描述" /></a></p>
    121. 

  121. <p>以此类推，最后就生成出来了这样一个图：</p>
    122. 

  122. <p><a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103210621487.png" alt="在这里插入图片描述" /></a></p>
    123. 

  123. <p>把没有标记的边删掉，就是最小生成树。 <a href="https://csacademy.com/app/graph_editor" target="_blank" rel="noopener" title="点击查看生成工具"><img src="https://img-blog.csdnimg.cn/20200103210727778.png" /></a></p>
    124. 

  124. <p>这就是prim算法 <del>，代码我不会写</del>在后面。</p>
    125. 

  125. <h3 id="生成方式二kruskal">生成方式二：kruskal</h3>
    126. 

  126. <p>这个算法本质上就是把所有边按照边权排序，然后直接<del>爆炸</del>按顺序判断要不要加进生成树里。 kruskal算法使用了一种极速闪电致命又自杀的东西：并查集。 <a href="https://schtonn.github.io/post/union-find-set" target="_blank" rel="noopener">他有多快呢？</a></p>
    127. 

  127. <hr />
    128. 

  128. <p>好了我们在建一个图模拟一下吧 <img src="https://img-blog.csdnimg.cn/20200103215213917.png" alt="在这里插入图片描述" /></p>
    129. 

  129. <p>先给边排序。最小的是<span class="math inline">\([2,3]\)</span>，把他拿出来，判断一下。怎么判断呢？首先访问一下并查集看一看，这个边连接的两个点在不在同一个集合内，不在的话就把这条边加入生成树，然后把两个点合并。否则忽略这一条变，继续。这一条边符合要求，加进并查集里，现在<span class="math inline">\({2,3}\)</span>是一个集合，剩下都是独立的。</p>
    130. 

  130. <p><img src="https://img-blog.csdnimg.cn/20200103215304212.png" alt="在这里插入图片描述" /> 现在最小的有<span class="math inline">\([1,4]\)</span>和<span class="math inline">\([4,5]\)</span>，我们都判断一下，都可以。 <img src="https://img-blog.csdnimg.cn/20200103215356204.png" alt="在这里插入图片描述" /></p>
    131. 

  131. <p>然后就是<span class="math inline">\([0,4]\)</span>和<span class="math inline">\([2,4]\)</span>，依然都是可以的。 <img src="https://img-blog.csdnimg.cn/20200103215507942.png" alt="在这里插入图片描述" /> 这样，一颗活灵活现的生成树就出现了。 <img src="https://img-blog.csdnimg.cn/20200103215600881.png" /></p>
    132. 

  132. <p>好了！</p>
    133. 

  133. <h3 id="代码luogup3366">代码（<a href="https://www.luogu.com.cn/problem/P3366" target="_blank" rel="noopener">luoguP3366</a>）</h3>
    134. 

  134. <p>kruskal的代码又短又易于理解，甚至可以直接用数组存边，所以他非常好写，推荐。</p>
    135. 

  135. <h4 id="prim">prim</h4>
    136. 

  136. <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"iostream"</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"queue"</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"cstring"</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> maxm 5000010</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> maxn 1000010</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> v,next,c;</span><br><span class="line">&#125;e[maxm&lt;&lt;<span class="number">1</span>];</span><br><span class="line"><span class="keyword">int</span> h[maxn],tot,n,m;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">adde</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v,<span class="keyword">int</span> c)</span></span>&#123;</span><br><span class="line">    tot++;</span><br><span class="line">    e[tot].v=v;</span><br><span class="line">    e[tot].c=c;</span><br><span class="line">    e[tot].next=h[u];</span><br><span class="line">    h[u]=tot;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">int</span> dis[maxn];</span><br><span class="line"><span class="keyword">bool</span> vis[maxn];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">qu</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> id,dis;</span><br><span class="line">    <span class="keyword">bool</span> <span class="keyword">operator</span> &lt; (<span class="keyword">const</span> qu t)<span class="keyword">const</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> dis&gt;t.dis;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">priority_queue&lt;qu&gt; q;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dijk</span><span class="params">(<span class="keyword">int</span> s)</span></span>&#123;</span><br><span class="line">    <span class="built_in">memset</span>(dis,<span class="number">0x3f</span>,<span class="keyword">sizeof</span>(dis));</span><br><span class="line">    <span class="built_in">memset</span>(vis,<span class="number">0</span>,<span class="keyword">sizeof</span>(vis));</span><br><span class="line">    <span class="keyword">while</span>(!q.empty())q.pop();</span><br><span class="line">    qu t;</span><br><span class="line">    t.dis=<span class="number">0</span>;</span><br><span class="line">    t.id=s;</span><br><span class="line">    dis[s]=<span class="number">0</span>;</span><br><span class="line">    q.push(t);</span><br><span class="line">    <span class="keyword">while</span>(!q.empty())&#123;</span><br><span class="line">        t=q.top();q.pop();</span><br><span class="line">        <span class="keyword">if</span>(vis[t.id])<span class="keyword">continue</span>;</span><br><span class="line">        vis[t.id]=<span class="literal">true</span>;</span><br><span class="line">        ans+=t.dis;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=h[t.id];j;j=e[j].next)&#123;</span><br><span class="line">            <span class="keyword">int</span> v=e[j].v;</span><br><span class="line">            <span class="keyword">if</span>(!vis[v]&amp;&amp;dis[v]&gt;e[j].c)&#123;</span><br><span class="line">                dis[v]=e[j].c;</span><br><span class="line">                qu now;</span><br><span class="line">                now.id=v;</span><br><span class="line">                now.dis=dis[v];</span><br><span class="line">                q.push(now);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> s=<span class="number">1</span>;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n&gt;&gt;m;</span><br><span class="line">    <span class="keyword">int</span> u,v,c;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)&#123;</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;u&gt;&gt;v&gt;&gt;c;</span><br><span class="line">        adde(u,v,c);</span><br><span class="line">adde(v,u,c);</span><br><span class="line">    &#125;</span><br><span class="line">    dijk(s);</span><br><span class="line"><span class="built_in">cout</span>&lt;&lt;ans&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
    137. 

  137. <h4 id="kruskal">kruskal</h4>
    138. 

  138. <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"iostream"</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"algorithm"</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> n,m,tot,sum,f[<span class="number">5001</span>];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span></span><br><span class="line">	<span class="keyword">int</span> u,v,c;</span><br><span class="line">&#125;a[<span class="number">200010</span>];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">cmp</span><span class="params">(<span class="keyword">const</span> node &amp;u,<span class="keyword">const</span> node &amp;v)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> u.c&lt;v.c;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getf</span><span class="params">(<span class="keyword">int</span> u)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(f[u]==u)<span class="keyword">return</span> u;</span><br><span class="line">	<span class="keyword">return</span> f[u]=getf(f[u]);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n&gt;&gt;m;</span><br><span class="line">	<span class="keyword">if</span>(m&lt;n<span class="number">-1</span>)&#123;<span class="built_in">cout</span>&lt;&lt;<span class="string">"orz"</span>&lt;&lt;<span class="built_in">endl</span>;<span class="keyword">return</span> <span class="number">0</span>;&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)<span class="built_in">cin</span>&gt;&gt;a[i].u&gt;&gt;a[i].v&gt;&gt;a[i].c;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)f[i]=i;</span><br><span class="line">	sort(a+<span class="number">1</span>,a+m+<span class="number">1</span>,cmp);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)&#123;</span><br><span class="line">		<span class="keyword">int</span> fu=getf(a[i].u),fv=getf(a[i].v);</span><br><span class="line">		<span class="keyword">if</span>(fu!=fv)&#123;</span><br><span class="line">            f[fu]=fv;</span><br><span class="line">			sum++;</span><br><span class="line">			tot+=a[i].c;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(sum==n<span class="number">-1</span>)<span class="keyword">break</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;tot&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
    139. 

  139. 

  140.       
    141. 

  141.     </div>
    142. 

  142.     <footer class="article-footer">
    143. 

  143.       <a data-url="http://yoursite.com/2020/03/01/min-span-tree/" data-id="ck7cjuv750005pc1346vq1oag" class="article-share-link">Share</a>
    144. 

  144.       
    145. 

  145.       
    146. 

  146.   <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>
    147. 

  147. 

  148.     </footer>
    149. 

  149.   </div>
    150. 

  150.   
    151. 

  151.     
    152. 

  152. <nav id="article-nav">
    153. 

  153.   
    154. 

  154.     <a href="/2020/03/02/dinic/" id="article-nav-newer" class="article-nav-link-wrap">
    155. 

  155.       <strong class="article-nav-caption">Newer</strong>
    156. 

  156.       <div class="article-nav-title">
    157. 

  157.         
    158. 

  158.           网络最大流-Dinic
    159. 

  159.         
    160. 

  160.       </div>
    161. 

  161.     </a>
    162. 

  162.   
    163. 

  163.   
    164. 

  164.     <a href="/2020/03/01/union-find/" id="article-nav-older" class="article-nav-link-wrap">
    165. 

  165.       <strong class="article-nav-caption">Older</strong>
    166. 

  166.       <div class="article-nav-title">并查集</div>
    167. 

  167.     </a>
    168. 

  168.   
    169. 

  169. </nav>
    170. 

  170. 

  171.   
    172. 

  172. </article>
    173. 

  173. 

  174. </section>
    175. 

  175.         
    176. 

  176.           <aside id="sidebar">
    177. 

  177.   
    178. 

  178.     
    179. 

  179. 

  180.   
    181. 

  181.     
    182. 

  182.   <div class="widget-wrap">
    183. 

  183.     <h3 class="widget-title">Tags</h3>
    184. 

  184.     <div class="widget">
    185. 

  185.       <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph/" rel="tag">graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/math/" rel="tag">math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/" rel="tag">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    186. 

  186.     </div>
    187. 

  187.   </div>
    188. 

  188. 

  189. 

  190.   
    191. 

  191.     
    192. 

  192.   <div class="widget-wrap">
    193. 

  193.     <h3 class="widget-title">Tag Cloud</h3>
    194. 

  194.     <div class="widget tagcloud">
    195. 

  195.       <a href="/tags/graph/" style="font-size: 20px;">graph</a> <a href="/tags/math/" style="font-size: 10px;">math</a> <a href="/tags/other/" style="font-size: 15px;">other</a> <a href="/tags/struct/" style="font-size: 10px;">struct</a>
    196. 

  196.     </div>
    197. 

  197.   </div>
    198. 

  198. 

  199.   
    200. 

  200.     
    201. 

  201.   <div class="widget-wrap">
    202. 

  202.     <h3 class="widget-title">Archives</h3>
    203. 

  203.     <div class="widget">
    204. 

  204.       <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    205. 

  205.     </div>
    206. 

  206.   </div>
    207. 

  207. 

  208. 

  209.   
    210. 

  210.     
    211. 

  211.   <div class="widget-wrap">
    212. 

  212.     <h3 class="widget-title">Recent Posts</h3>
    213. 

  213.     <div class="widget">
    214. 

  214.       <ul>
    215. 

  215.         
    216. 

  216.           <li>
    217. 

  217.             <a href="/2020/03/02/segment-tree/">线段树</a>
    218. 

  218.           </li>
    219. 

  219.         
    220. 

  220.           <li>
    221. 

  221.             <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
    222. 

  222.           </li>
    223. 

  223.         
    224. 

  224.           <li>
    225. 

  225.             <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
    226. 

  226.           </li>
    227. 

  227.         
    228. 

  228.           <li>
    229. 

  229.             <a href="/2020/03/01/min-span-tree/">最小生成树</a>
    230. 

  230.           </li>
    231. 

  231.         
    232. 

  232.           <li>
    233. 

  233.             <a href="/2020/03/01/union-find/">并查集</a>
    234. 

  234.           </li>
    235. 

  235.         
    236. 

  236.       </ul>
    237. 

  237.     </div>
    238. 

  238.   </div>
    239. 

  239. 

  240.   
    241. 

  241. </aside>
    242. 

  242.         
    243. 

  243.       </div>
    244. 

  244.       <footer id="footer">
    245. 

  245.   
    246. 

  246.   <div class="outer">
    247. 

  247.     <div id="footer-info" class="inner">
    248. 

  248.       &copy; 2020 Schtonn<br>
    249. 

  249.       Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    250. 

  250.     </div>
    251. 

  251.   </div>
    252. 

  252. </footer>
    253. 

  253.     </div>
    254. 

  254.     <nav id="mobile-nav">
    255. 

  255.   
    256. 

  256.     <a href="/" class="mobile-nav-link">Home</a>
    257. 

  257.   
    258. 

  258.     <a href="/archives" class="mobile-nav-link">Archives</a>
    259. 

  259.   
    260. 

  260. </nav>
    261. 

  261.     
    262. 

  262. 

  263. <script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
    264. 

  264. 

  265. 

  266.   
    267. 

  267. <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
    268. 

  268. 

  269.   
    270. 

  270. <script src="/fancybox/jquery.fancybox.pack.js"></script>
    271. 

  271. 

  272. 

  273. 

  274. 

  275. <script src="/js/script.js"></script>
    276. 

  276. 

  277. 

  278. 

  279. 

  280.   </div>
    281. 

  281. </body>
    282. 

  282. </html>
    283.