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

這是依商業技藝競賽程式104年正式題第4題子題2稍微修改
資料檔第1列 一個數字 n ，代表 n 組資料，接著每組資料一列
每一列為一個圖形所有「邊」以空格隔開，「邊」由3個以逗號隔開的數字組成{2個節點及成本}
每組資料印出1個數字，算出圖形的最小成本生成樹的成本。

參考程式碼：

'最小成本生成樹 MST

Const MaxM As Integer = 20 '最多20邊

Const MaxN As Integer = 26 '最多26點

Dim eg(MaxM) As String '邊

Dim ct(MaxM) As Integer  '成本

Dim rt(MaxN) '此點的根

Dim ht(MaxN) '此點的高

Dim n As Integer '節點數

Dim m As Integer '邊數

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

 FileOpen(1, "in1.txt", OpenMode.Input)

 ' FileOpen(2, "in2.txt", OpenMode.Input)

 FileOpen(3, "out.txt", OpenMode.Output)

 For fn = 1 To 1 'in1,in2合成一個

    If fn = 2 Then PrintLine(3)

    Dim t As Short = LineInput(fn)

    For i = 1 To t

       Dim egs() = LineInput(fn).Split(" ")   '一列為一個樹，多個邊

       m = egs.Length  '邊數

       For j = 0 To m - 1

          eg(j) = Strings.Left(egs(j), 3)  '一個邊

          ct(j) = Val(Mid(egs(j), 5))  ' 這個邊的 成本

       Next

        Array.Sort(ct, eg, 0, m)

        Array.Clear(ht, 0, MaxN)

        For j = 0 To MaxN

             rt(j) = j

        Next

        Dim ans = 0

        For j = 0 To m - 1

          Dim x As Integer = Asc(Mid(eg(j), 1, 1)) - 65

          Dim y As Integer = Asc(Mid(eg(j), 3, 1)) - 65

          If same(x, y) Then Continue For

          ans += ct(j)  '不是同一 根 就將成本加入 ans

          uni(x, y) '將x,y合併

          Print(3, "+" & ct(j) & eg(j) & " ") '測試用列印

        Next

        PrintLine(3, "ans=" & ans)  '測試用列印

     Next i

  Next fn

  End

End Sub

 Function fdrt(ByVal x As Integer) As Integer  '找 x 的根

        If rt(x) = x Then Return x

        rt(x) = fdrt(rt(x))

        Return rt(x)

 End Function

 Function same(ByVal x As Integer, ByVal y As Integer)

        Return (fdrt(x) = fdrt(y))  ' x,y 的根是否相同

 End Function

 Sub uni(ByVal x As Integer, ByVal y As Integer)  '將 x樹 及 y樹 合成一樹

        x = fdrt(x) : y = fdrt(y)

        If x = y Then Return

        If ht(x) < ht(y) Then

            rt(x) = y

        Else

            rt(y) = x

            If ht(x) = ht(y) Then ht(x) += 1

        End If

 End Sub

'輸入 in1.txt 併 in2 

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

輸出：第1組 31 , 第2組 7 , 第3組 29 , 第4組 3

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