Ứng dụng thuật toán Prim giải bài toán xây dựng đường sắt bằng C/C++

Ứng dụng thuật toán Prim giải bài toán xây dựng đường sắt bằng C/C++

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;

 }

 

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (3 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Apple kiện Kindle vi phạm bản quyền App Store

Apple kiện Kindle vi phạm bản quyền App Store

Công ty sản xuất máy tính Apple mới đây đã thay đổi đơn kiện Amazon với cáo buộc hãng cung cấp dịch vụ thương mại điện tử này vi phạm bản quyền thương hiệu App Store

Google Ngừng Cung Cấp Ứng Dụng Gmail Cho BlackBerry Từ Ngày 22/11

Google Ngừng Cung Cấp Ứng Dụng Gmail Cho BlackBerry Từ Ngày 22/11

Điều này có nghĩa là họ sẽ không phát triển thêm và hỗ trợ kỹ thuật cho ứng dụng này trong tương lai nữa, tuy nhiên những điện thoại này đang được cài ...

Bí quyết trốn thoát khỏi Facebook Timeline

Bí quyết trốn thoát khỏi Facebook Timeline

Nếu thực sự bức xúc với giao diện mới, bạn hãy cài trình duyệt IE7 xem sao.