Ứ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 (4 votes)
Ảnh của Tommy Tran

Tommy 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

Bình luận (1)

Ảnh của Tommy Tran
Tommy Tran- Jul 20, 2023 10:57 AM Reply

Hi mọi người, mình có bài toán về lựa chọn công cụ về data pipeline cần mn giúp đỡ.

Nguồn dữ liệu là Redshift DB từ 1 account khác, có enable Data Sharing

Đích là Redshift DB bên mình

Data cần xử lý là dạng bảng, số lượng trên 1 trăm và total size chưa nén tầm hơn 100 GB. Transformation từ nguồn tới đích chủ yếu là join table, aggregate, clean…

Mình phân vân 2 hướng sau

Cách 1: Sử dụng SQL procedure trên Redshift đầu đích để transform. Orchestrate bằng Step Functions + Lambda call các SP. Cách này m thấy cost khá thấp tuy nhiên để step functions call tới các SP trên redshift lại hơi phức tạp.

Cách 2: Dùng Glue, connect nguồn và đích bằng jdbc, dùng glue transform… mình chưa dùng Glue end to end nhưng mình đã dùng Spark và hiểu join table lớn yêu cầu suffle data giữa các node rất nhiều nên performance khá kém.

Có thể có cách khác tối ưu hơn, nhờ mn tư vấn thêm nhé. Thanks in advance

 

Add Comment

Filtered HTML

  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Các thẻ HTML được chấp nhận: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Tự động ngắt dòng và đoạn văn.

Plain text

  • No HTML tags allowed.
  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Tự động ngắt dòng và đoạn văn.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Enter the characters shown in the image.

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

 
5 Videos mới cần thiết để Working với Blocks trong Drupal 8

5 Videos mới cần thiết để Working với Blocks trong Drupal 8

Next week we'll start digging into the State API to get more parts of our block moved over. Have a great week and enjoy!

Huawei Vision Running Android 2.3 Gingerbread

Huawei Vision Running Android 2.3 Gingerbread

Huawei has been pushing through with their low-cost android devices. Now, they are coming with Huawei Vision.

Add-on Firefox hay dành cho seo và webmaster

Để làm SEO cho tốt, webmaster thường xuyên theo dõi tình hình tăng giảm thứ hạng về site của mình cũng như các site đối thủ, những thông tin như ranking, backlink, income links

Công ty diệt chuột T&C

 

Diet con trung