frmmain.frm

在八个城市之间建造电视微波中继站

VERSION 5.00
Begin VB.Form frmMain 
   AutoRedraw      =   -1  'True
   Caption         =   "生成最小生成树              作者：冯玉强 刘春杰"
   ClientHeight    =   5445
   ClientLeft      =   60
   ClientTop       =   345
   ClientWidth     =   7110
   LinkTopic       =   "Form1"
   LockControls    =   -1  'True
   ScaleHeight     =   5445
   ScaleWidth      =   7110
   StartUpPosition =   2  '屏幕中心
   Begin VB.CommandButton Command3 
      Caption         =   "退出"
      Height          =   495
      Left            =   4200
      TabIndex        =   28
      Top             =   4560
      Width           =   735
   End
   Begin VB.CommandButton Command2 
      Caption         =   "初始化"
      Height          =   495
      Left            =   2640
      TabIndex        =   11
      Top             =   4560
      Width           =   735
   End
   Begin VB.PictureBox Pp 
      Height          =   3975
      Left            =   2160
      ScaleHeight     =   3915
      ScaleWidth      =   4515
      TabIndex        =   1
      Top             =   240
      Width           =   4575
      Begin VB.CommandButton City 
         Caption         =   "8"
         Height          =   255
         Index           =   8
         Left            =   3240
         TabIndex        =   10
         Top             =   3120
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "7"
         Height          =   255
         Index           =   7
         Left            =   3240
         TabIndex        =   9
         Top             =   1800
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "6"
         Height          =   255
         Index           =   6
         Left            =   3240
         TabIndex        =   8
         Top             =   360
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "5"
         Height          =   255
         Index           =   5
         Left            =   1920
         TabIndex        =   7
         Top             =   2400
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "4"
         Height          =   255
         Index           =   4
         Left            =   1920
         TabIndex        =   6
         Top             =   1080
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "3"
         Height          =   255
         Index           =   3
         Left            =   720
         TabIndex        =   5
         Top             =   3120
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "2"
         Height          =   255
         Index           =   2
         Left            =   720
         TabIndex        =   4
         Top             =   1800
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "1"
         Height          =   255
         Index           =   1
         Left            =   720
         TabIndex        =   3
         Top             =   360
         Width           =   255
      End
      Begin VB.CommandButton City 
         Caption         =   "0"
         Height          =   255
         Index           =   0
         Left            =   0
         TabIndex        =   2
         Top             =   3840
         Visible         =   0   'False
         Width           =   255
      End
      Begin VB.Label Label15 
         Caption         =   "3"
         Height          =   255
         Left            =   2520
         TabIndex        =   27
         Top             =   2760
         Width           =   255
      End
      Begin VB.Label Label14 
         Caption         =   "7"
         Height          =   255
         Left            =   2040
         TabIndex        =   25
         Top             =   1800
         Width           =   135
      End
      Begin VB.Label Label13 
         Caption         =   "2"
         Height          =   255
         Left            =   1320
         TabIndex        =   24
         Top             =   1440
         Width           =   255
      End
      Begin VB.Label Label12 
         Caption         =   "6"
         Height          =   255
         Left            =   2640
         TabIndex        =   23
         Top             =   840
         Width           =   255
      End
      Begin VB.Label Label11 
         Caption         =   "4"
         Height          =   255
         Left            =   1440
         TabIndex        =   22
         Top             =   840
         Width           =   255
      End
      Begin VB.Label Label10 
         Caption         =   "7"
         Height          =   255
         Left            =   2640
         TabIndex        =   21
         Top             =   1560
         Width           =   255
      End
      Begin VB.Label Label9 
         Caption         =   "5"
         Height          =   255
         Left            =   1200
         TabIndex        =   20
         Top             =   2640
         Width           =   255
      End
      Begin VB.Label Label8 
         Caption         =   "7"
         Height          =   135
         Left            =   2040
         TabIndex        =   19
         Top             =   3120
         Width           =   135
      End
      Begin VB.Label Label7 
         Caption         =   "13"
         Height          =   375
         Left            =   1320
         TabIndex        =   18
         Top             =   2160
         Width           =   255
      End
      Begin VB.Label Label6 
         Caption         =   "11"
         Height          =   375
         Left            =   2640
         TabIndex        =   17
         Top             =   2280
         Width           =   255
      End
      Begin VB.Label Label5 
         Caption         =   "5"
         Height          =   255
         Left            =   3360
         TabIndex        =   16
         Top             =   2520
         Width           =   135
      End
      Begin VB.Label Label4 
         Caption         =   "4"
         Height          =   255
         Left            =   3480
         TabIndex        =   15
         Top             =   1200
         Width           =   135
      End
      Begin VB.Label Label3 
         Caption         =   "10"
         Height          =   255
         Left            =   720
         TabIndex        =   14
         Top             =   2400
         Width           =   255
      End
      Begin VB.Label Label2 
         Caption         =   "6"
         Height          =   255
         Left            =   840
         TabIndex        =   13
         Top             =   1200
         Width           =   135
      End
      Begin VB.Label Label1 
         Caption         =   "9"
         Height          =   255
         Left            =   2040
         TabIndex        =   12
         Top             =   360
         Width           =   135
      End
   End
   Begin VB.CommandButton Command1 
      Caption         =   "运行"
      Height          =   495
      Left            =   3360
      TabIndex        =   0
      Top             =   4560
      Width           =   855
   End
   Begin VB.Label Label17 
      Caption         =   "题目："
      Height          =   255
      Left            =   120
      TabIndex        =   30
      Top             =   480
      Width           =   615
   End
   Begin VB.Label Label16 
      Caption         =   "Label16"
      Height          =   2535
      Left            =   120
      TabIndex        =   29
      Top             =   960
      Width           =   1815
   End
   Begin VB.Label label 
      Height          =   375
      Left            =   5160
      TabIndex        =   26
      Top             =   4680
      Width           =   1575
   End
End
Attribute VB_Name = "frmMain"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
Option Explicit
Private Type LJ
  i As Integer
  j As Integer
  w As Integer
  flag As Boolean
  
End Type
Private Type code
  self As Integer
  father As Integer
End Type
Dim xx(16) As LJ '边
Dim cod(9) As code '根节点


Private Sub PL(i As Integer, j As Integer)
   Dim xx1, xx2, yy1, yy2 As Integer
   xx1 = City(i).Left + 0.5 * City(i).Width
   yy1 = City(i).Top + 0.5 * City(i).Height
   xx2 = City(j).Left + 0.5 * City(j).Width
   yy2 = City(j).Top + 0.5 * City(j).Height
   Pp.Line (xx1, yy1)-(xx2, yy2), RGB(0, 0, 255)
   
End Sub
Private Sub PL2(i As Integer, j As Integer)
   Dim xx1, xx2, yy1, yy2 As Integer
   xx1 = City(i).Left + 0.5 * City(i).Width
   yy1 = City(i).Top + 0.5 * City(i).Height
   xx2 = City(j).Left + 0.5 * City(j).Width
   yy2 = City(j).Top + 0.5 * City(j).Height
   Pp.Line (xx1, yy1)-(xx2, yy2), RGB(255, 0, 0)
   
End Sub


Private Sub Command1_Click()
   Dim total As Integer
   Dim num As Integer
   total = 0 '总费用
   num = 0 '记录最小生成树的边数
  
   Dim i As Integer
   For i = 0 To 8
     cod(i).self = i
     cod(i).father = 0
   Next
   Dim min As Integer
   
   Dim x As Integer
   Dim y As Integer
   While num < 7
ooo: min = Minum()
     x = xx(min).i
     y = xx(min).j
     If SBoot(x) = SBoot(y) Then
       xx(min).flag = True
      ' MsgBox min & " error"
       GoTo ooo
     Else
       cod(SBoot(y)).father = SBoot(x)
       total = total + xx(min).w
       Call PL2(x, y)
       num = num + 1
       xx(min).flag = True
       
       
beep:       beep: beep
       'MsgBox x & "," & y & "," & total
     End If
     
     
   Wend
   
   label.Caption = "总费用为" & total
End Sub


Private Sub Command2_Click()
   label.Caption = ""
  
   Call PL(1, 2)
   Call PL(1, 4)
   Call PL(1, 6)
   Call PL(2, 4)
   Call PL(4, 6)
   Call PL(2, 3)
   Call PL(2, 5)
   Call PL(4, 5)
   Call PL(4, 7)
   Call PL(6, 7)
   Call PL(7, 8)
   Call PL(5, 7)
   Call PL(5, 8)
   Call PL(3, 5)
   Call PL(3, 8)
   With xx(0)
    .i = 10
    .j = 10
    .w = 100
   End With

   With xx(1)
    .i = 1
    .j = 2
    .w = 6
   End With
   With xx(2)
    .i = 1
    .j = 4
    .w = 4
   End With
   With xx(3)
    .i = 1
    .j = 6
    .w = 9
   End With
   With xx(4)
    .i = 2
    .j = 4
    .w = 2
   End With
   With xx(5)
    .i = 6
    .j = 4
    .w = 6
   End With
   With xx(6)
    .i = 6
    .j = 7
    .w = 4
   End With
   With xx(7)
    .i = 4
    .j = 7
    .w = 7
   End With
   With xx(8)
    .i = 5
    .j = 7
    .w = 11
   End With
   With xx(9)
    .i = 7
    .j = 8
    .w = 5
   End With
   With xx(10)
    .i = 2
    .j = 5
    .w = 13
   End With
   With xx(11)
    .i = 5
    .j = 8
    .w = 3
   End With
   With xx(12)
    .i = 3
    .j = 8
    .w = 7
   End With
   With xx(13)
    .i = 3
    .j = 5
    .w = 5
   End With
   With xx(14)
    .i = 2
    .j = 3
    .w = 10
   End With
   With xx(15)
    .i = 4
    .j = 5
    .w = 7
   End With
   Dim ii As Integer
   For ii = 0 To 15
     xx(ii).flag = False
   Next ii
   Command1.Enabled = True
End Sub


Private Function SBoot(x As Integer) As Integer
   Dim temp As Integer
   Dim pa As Integer
   pa = x
   temp = cod(x).father
   While temp <> 0
      pa = temp
      temp = cod(pa).father
   Wend
   SBoot = pa
End Function


Private Function Minum() As Integer
   Dim min As Integer
   Dim i As Integer
   min = 1
   While xx(min).flag = True And min <= 14
     min = min + 1
   Wend
   For i = min To 15
     If xx(i).flag = False Then
       If xx(i).w < xx(min).w Then min = i
     End If
   Next
   Minum = min
End Function

Private Sub Command3_Click()
   Unload Me
End Sub


Private Sub Form_Load()
   Label16.Caption = "在八个城市之间建造电视微波中继站，如图是可行线路，弧旁数字为费用。试建在哪个城市可实现连通每个城市且费用为最低"
   Command1.Enabled = False
End Sub