[Bài toán] Xây dựng đường sắt

Bài toán: Bộ xây dựng đang có kế hoạch xây dựng hệ thống đường sắt nối liền các thành phố với nhau, sao cho chỉ có duy nhất 1 tuyến đường sắt nối liền hai thành phố bất kỳ. Sau khi nhiên cứu tính toán chi phí xây dựng các tuyến đường sắt nối liền các thành phố, bộ xây dựng thu được ma trận chi phí hai chiều.
Hãy giúp bộ xây dựng xây dựng xây dựng hệ thống đường sắt với yêu cầu trên với chi phí xây dựng nhỏ nhất.
[Input]
Dữ liệu đầu vào được chứa trong file WELLPROJECT.INP, dòng đầu chứa số lượng test case T ( T ≤ 10). Tiếp đó là N - Số thành phố. N dòng tiếp theo là ma trận chi phí xây dựng đường sắt nối liền 2 thành phố bất kỳ.
[Output]
In ra file WELLPROJECT.OUT chi phí nhỏ nhất xây dựng hệ thống đướng sắt trên. Kết quả của mỗi test case đươc in ra trên một dòng.
[Input example]
5
3
0 1 4
1 0 2
4 2 0
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
6
0 45 86 12 61 51
45 0 80 99 18 2
86 80 0 9 37 14
12 99 9 0 14 90
61 18 37 14 0 52
51 2 14 90 52 0
10
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0
10
0 40613 19297 99549 27948 50416 95139 82856 99082 79380
40613 0 96888 46784 65549 8396 18128 31348 94809 16773
19297 96888 0 83011 20456 42383 34635 86957 85569 95179
99549 46784 83011 0 24003 66861 44068 11524 97968 22654
27948 65549 20456 24003 0 16590 54758 37348 62125 17814
50416 8396 42383 66861 16590 0 67234 14142 90848 64960
95139 18128 34635 44068 54758 67234 0 81632 81223 19101
82856 31348 86957 11524 37348 14142 81632 0 38508 16462
99082 94809 85569 97968 62125 90848 81223 38508 0 37607
79380 16773 95179 22654 17814 64960 19101 16462 37607 0
[Output example]
3
28
51
9
162602
Chương trình giải bài toán trên được cài đặt theo thuật toán Prim như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define NMax 101
int map[NMax][NMax];
bool isVisited[NMax];
#define LENGTHMAX 1000000
int main(){
 freopen("WELLPROJECT.INP","r", stdin);
 freopen("WELLPROJECT.OUT","w", stdout);
 int T;
 cin>>T;
 for(int tc = 0; tc < T; tc++){
  int verticeCount;
  cin>>verticeCount;
  for(int i =1; i<= verticeCount; i++){
   // khởi tạo giá trị mảng visited.
   isVisited[i] = false;
   for(int j= 1;j <= verticeCount ; j++){
    cin>>map[i][j];
   }
  }
  // Prim algorithm.
  // bắt đầu từ đỉnh 1.
  isVisited[1] = true;
  int countEdge = 0;
  int sumOfEdge = 0;
  // Vòng lặp, thăm các đỉnh để tạo cây khung nhỏ nhất.
  while(countEdge < verticeCount - 1){
   int tempLength = LENGTHMAX;
   int tempVertice = 1;
   for(int i=1 ;i <= verticeCount; i++){
    if(isVisited[i]){
     for(int j=1; j <= verticeCount ; j++){
      if(j != i && !isVisited[j] && map[i][j] > 0 && map[i][j] < tempLength){
       tempLength = map[i][j];
       tempVertice = j;
      }
     }
    }
   }
   countEdge++;
   isVisited[tempVertice]= true;
   sumOfEdge += tempLength;
  }
  cout<<sumOfEdge<<endl;
 }

}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.