//这里使用无向图 #include <iostream> using namespace std; const int MAXN = 2001; const int INF = ; int n,e; int w[MAXN][MAXN]; int mincount[MAXN]; //从初始顶点到该顶点的最小权值
讯享网 void init() { 
讯享网</span><span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> i,j; </span><span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> tx,ty; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i = <span style="color: rgba(128, 0, 128, 1)">0</span>; i&lt;=MAXN; i++<span style="color: rgba(0, 0, 0, 1)">) </span><span style="color: rgba(0, 0, 255, 1)">for</span>(j =<span style="color: rgba(128, 0, 128, 1)">0</span>; j&lt;MAXN; j++<span style="color: rgba(0, 0, 0, 1)">) w[i][j] </span>=<span style="color: rgba(0, 0, 0, 1)"> INF; cin </span>&gt;&gt; n &gt;&gt;<span style="color: rgba(0, 0, 0, 1)"> e; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i = <span style="color: rgba(128, 0, 128, 1)">1</span>; i&lt;=e; i++<span style="color: rgba(0, 0, 0, 1)">) { cin </span>&gt;&gt; tx &gt;&gt; ty &gt;&gt;<span style="color: rgba(0, 0, 0, 1)"> w[tx][ty]; w[tx][ty] </span>=<span style="color: rgba(0, 0, 0, 1)"> w[ty][tx]; } 
 } void prim(int s) //从标号为s处开始生成树 { 
</span><span style="color: rgba(0, 0, 255, 1)">int</span> i,j,cnt = <span style="color: rgba(128, 0, 128, 1)">0</span>,min; <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> cnt 是生成树所有边的权值之和</span> <span style="color: rgba(0, 0, 255, 1)">int</span><span style="color: rgba(0, 0, 0, 1)"> k; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i = <span style="color: rgba(128, 0, 128, 1)">1</span>; i&lt;= n; i++<span style="color: rgba(0, 0, 0, 1)">) mincount[i] </span>= w[s][i]; <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 初始化，设w[1][i]是初始点k到i的最小权值，如果没有就设为INF</span> mincount[s] = <span style="color: rgba(128, 0, 128, 1)">0</span><span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(i = <span style="color: rgba(128, 0, 128, 1)">1</span>; i &lt; n; i++) <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">一共有n-1次</span> 
  { 
讯享网 min </span>=<span style="color: rgba(0, 0, 0, 1)"> INF; </span><span style="color: rgba(0, 0, 255, 1)">for</span>(j = <span style="color: rgba(128, 0, 128, 1)">1</span>; j &lt;= n; j++<span style="color: rgba(0, 0, 0, 1)">) { </span><span style="color: rgba(0, 0, 255, 1)">if</span>(mincount[j]!=<span style="color: rgba(128, 0, 128, 1)">0</span> &amp;&amp; mincount[j]&lt;<span style="color: rgba(0, 0, 0, 1)">min) { min </span>=<span style="color: rgba(0, 0, 0, 1)"> mincount[j]; k </span>= j; <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">记录该点</span> 
  } 
 mincount[k] </span>= <span style="color: rgba(128, 0, 128, 1)">0</span>;<span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">将该点加入到最小生成树中</span> cnt += min; <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">将这条边权值加入到最小生成树中</span> <span style="color: rgba(0, 0, 255, 1)">for</span>(j = <span style="color: rgba(128, 0, 128, 1)">1</span>;j&lt;=n;j++) <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">修正初始点到每个点的最小权值</span> 
  { 
讯享网 </span><span style="color: rgba(0, 0, 255, 1)">if</span>(w[k][j]&lt;<span style="color: rgba(0, 0, 0, 1)">mincount[j]) mincount[j] </span>=<span style="color: rgba(0, 0, 0, 1)"> w[k][j]; } } } cout </span>&lt;&lt; cnt &lt;&lt;<span style="color: rgba(0, 0, 0, 1)"> endl; 
 } int main() { 
init(); prim(</span><span style="color: rgba(128, 0, 128, 1)">1</span><span style="color: rgba(0, 0, 0, 1)">); </span><span style="color: rgba(0, 0, 255, 1)">return</span> <span style="color: rgba(128, 0, 128, 1)">0</span><span style="color: rgba(0, 0, 0, 1)">; 
 }