http://158.108.32.49/wiki/index.php?action=history&feed=atom&title=Algo_lab%2Fmst 2026-05-07T00:21:39Z ประวัติรุ่นแก้ไขของหน้านี้ในวิกิ MediaWiki 1.33.1 http://158.108.32.49/wiki/index.php?title=Algo_lab/mst&diff=59468&oldid=prev 2023-10-30T07:02:42Z

<p>สร้างหน้าด้วย &quot;&lt;syntaxhighlight lang=&quot;cpp&quot;&gt; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; int n,m; vector&lt;int&gt; u,v; vector&lt;int&gt; weig...&quot;</p> <p><b>หน้าใหม่</b></p><div>&lt;syntaxhighlight lang=&quot;cpp&quot;&gt;<br /> #include &lt;iostream&gt;<br /> #include &lt;vector&gt;<br /> #include &lt;algorithm&gt;<br /> <br /> using namespace std;<br /> <br /> int n,m;<br /> vector&lt;int&gt; u,v;<br /> vector&lt;int&gt; weights;<br /> vector&lt;pair&lt;int,int&gt;&gt; ew;<br /> <br /> void read_input()<br /> {<br /> cin &gt;&gt; n &gt;&gt; m;<br /> for(int i=0; i&lt;m; i++) {<br /> int a,b,w;<br /> cin &gt;&gt; a &gt;&gt; b &gt;&gt; w;<br /> a--; b--;<br /> u.push_back(a);<br /> v.push_back(b);<br /> weights.push_back(w);<br /> <br /> ew.push_back(make_pair(w,i));<br /> }<br /> }<br /> <br /> const int MAX_N = 200010;<br /> int parents[MAX_N];<br /> int ranks[MAX_N];<br /> void init_union_find()<br /> {<br /> for(int i=0; i&lt;n; i++) {<br /> parents[i] = i;<br /> ranks[i] = 1;<br /> }<br /> }<br /> int find(int x) <br /> { <br /> if(parents[x]==x) {<br /> return x;<br /> } else {<br /> return find(parents[x]);<br /> }<br /> }<br /> void union_sets(int x, int y) <br /> {<br /> if(parents[x] == parents[y]) {<br /> return;<br /> }<br /> int py = find(y);<br /> int px = find(x);<br /> if(ranks[px] &gt; ranks[py]) {<br /> parents[py] = px;<br /> } else if(ranks[py] &gt; ranks[px]) {<br /> parents[px] = py;<br /> } else {<br /> parents[py] = px;<br /> ranks[px]++;<br /> }<br /> }<br /> <br /> int main()<br /> {<br /> read_input();<br /> sort(ew.begin(), ew.end());<br /> init_union_find();<br /> <br /> int total_weight = 0;<br /> <br /> for(int i=0; i&lt;m; i++) {<br /> int e = ew[i].second; // end points are u[e] and v[e]<br /> <br /> if(find(u[e]) != find(v[e])) {<br /> // add e to our solution<br /> <br /> total_weight += weights[e];<br /> union_sets(u[e], v[e]);<br /> }<br /> }<br /> <br /> cout &lt;&lt; total_weight &lt;&lt; endl;<br /> return 0;<br /> }<br /> <br /> &lt;/syntaxhighlight&gt;</div>

Jittat