商競104F-P42最小成本生成樹(CPP參考)

這是依商業技藝競賽程式104年正式題第4題子題2稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料一列
每一列為一個圖形所有「邊」以空格隔開，「邊」由3個以逗號隔開的數字組成{2個節點及成本}
每組資料印出1個數字，算出圖形的最小成本生成樹的成本。
參考程式碼：
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
const int MaxM = 20;  //最多 20 邊
const int MaxN = 26;  //最多 26 點
struct egs
{
int k;  // 成本
int a,b;  // a-b 相鄰
} eg[MaxM];
int rt[MaxN];  // 根
int ht[MaxN];  // 高
bool cmp(egs x, egs y)  //結構為 egs 的資料型別 x , y 比較大小(x<y傳回真)
{
return x.k<y.k;
}
int val(string t)  //字串數 轉為數值
{
  int k=t.size();
  int i,v=0;
  for(i=0; i<k; ++i)
    if(t[i]>='0' && t[i]<='9')
   v = v*10 + t[i]-'0';
  return v;
}
int n,m; // n 節點、m邊
int fdrt(int x) // 找 x 的根
{
if( rt[x] == x ) return x;
return ( rt[x] = fdrt(rt[x]) );
}
void uni(int x, int y) // x樹 及 y樹 合併
{
x=fdrt(x) ; y=fdrt(y);
if( x==y ) return;
if( ht[x] < ht[y] ) rt[x] = y;
else
{
rt[y] = x;
if(rt[x] == rt[y]) ht[x]++;
}
}
bool same(int x, int y)
{
return fdrt(x) == fdrt(y);
}
int main(void)
{
   int t,i,j;
   int x,y,k;
   string line,s;
   cin >> t; getline(cin,line);
   while( t-- )
   {
// init
n=0; m=0;
for(i=0; i<MaxN; ++i)
{
rt[i] = i;
ht[i] = 0;
}
getline(cin,line);
istringstream sin(line);
while( sin >> s )
{
x = s[0] -'A';  y = s[2] -'A';
k = val( s.substr(4) );
// cout << x <<'-' << y << ':' << k <<' ';  //
eg[m].a = x;  eg[m].b = y; eg[m].k = k;
m++;
}
// cout << endl;  //
sort(eg , eg+m, cmp);
// for(i=0; i<m; ++i)
//   cout << eg[i].k <<':' << eg[i].a << '-' << eg[i].b <<' ';
// cout << endl;
int ans=0;
for(i=0; i<m; ++i)
{
x = eg[i].a;  y = eg[i].b;  k = eg[i].k;
if( same(x,y) ) continue;
ans += k;
uni(x,y);   // x樹 及 y樹 合併
// cout << '+' <<k<<':'<<x<<'-'<<y<<'='<<ans<<' ';
}
// cout <<" ans=" << ans << endl;
   }
return 0;
}
/*範例輸入
4
A,B,6 A,E,9 B,C,3 B,D,5 C,D,7 B,F,8 D,E,10 D,F,11 A,F,12 E,F,15
A,B,3 A,C,2 B,C,1 B,D,2 C,D,1 B,E,2 C,F,1 D,E,1 D,F,1 D,G,2 E,G,1 F,G,1
B,A,6 B,F,8 B,D,5 D,E,10 D,F,9 A,F,12 A,E,10 E,F,15
D,E,1 D,G,2 D,F,1 E,G,1 F,G,1
範例輸出 ------
31
7
29
3
---參考
+3B,C +5B,D +6A,B +8B,F +9A,E ans=31
+1C,D +1D,F +1D,E +1F,G +1B,C +2A,C ans=7
+5B,D +6B,A +8B,F +10A,E ans=29
+1E,G +1F,G +1D,F ans=3
*/