Bài toán xây dựng đường sắt được cài đặt theo thuật toán Prim và C/C++

Bài toán xây dựng đường sắt được cài đặt theo thuật toán Prim và 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?: 
No votes yet
Ả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

 
Tìm hiểu một vài điểm cấu hình của Varnish rất hay cho Drupal 8

Tìm hiểu một vài điểm cấu hình của Varnish rất hay cho Drupal 8

In this article we would like to share some use cases and recipes for configuring Varnish.

Cập nhật hứơng dẫn SEO với 301 Redirect

Cập nhật hứơng dẫn SEO với 301 Redirect

Ắt hẳn khi thực hiện seo từ khóa, bạn sẽ gặp phải trường hợp một URL bạn đã chăm chút để đạt thứ hạng cao trên công cụ tìm kiếm, nhưng giờ URL đó lại bị thay đổi (do cập nhật website, ngôn ngữ mới, trang gốc bị xóa…). Bài viết này sẽ giúp bạn thực hiện điều đó.

Anonymous tiết lộ danh tính kẻ dọa xóa sổ Facebook

Anonymous tiết lộ danh tính kẻ dọa xóa sổ Facebook

Nhóm tin tặc nổi tiếng nhất toàn cầu cảm thấy bức xúc trước phản ứng của mọi người về vụ tấn công có thể diễn ra hôm nay và ...