[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;
 }

}

[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây bao trùm nhỏ nhất cần tìm.
    Trong quá trình thực hiện thuật toán, ở mỗi bước, ta có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị được sẽ được gán các nhãn. Nhãn của một đỉnh v gồm hai phần, [d[v], near[v]]. Trong đó, phần thứ nhất d[v] dùng để ghi nhận độ dài cạnh nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng. Phần thứ hai, near[v] ghi nhận đỉnh của cây khung gần v nhất. Thuật toán Prim được mô tả thông qua thủ tục sau:

void Prim(void){
 /*bước khởi tạo*/
 Chọn s là một đỉnh nào đó của đồ thị;
 VH = { s }; T = φ; d[s] = 0; near[s] = s;
 For(v∈V\VH) {
  D[v] = C[s, v]; near[v] = s;
 }
 /* Bước lặp */
 Stop = False;
 While(not stop) {
  Tìm u∈V\VH thoả mãn: d[u] = min{ d[v] với u∈V\VH };
  VH = VH∪{ u }; T = T ∪(u, near[u]);
  If(| VH | ) == n ) {
  H = <VH, T> là cây khung nhỏ nhất của đồ thị;
  Stop = TRUE;
  }Else{
   For(v ∈V\VH) {
    If(d[v] > C[u, v]) {
     D[v] = C[u, v];
     Near[v] = u;
    }
   }
  }
 }
}

Chương trình cài đặt thuật toán Prim tìm cây bao trùm nhỏ nhất được thực hiện như sau:

Tìm cây khung nhỏ nhất với thuật toán Prim

#include<iostream>
#include<conio.h>
using namespace std;
#define TRUE 1 
#define FALSE  0 
#define MAX  10000 
int a[100][100];//ma trận trọng số của đồ thị.
int n;//số đỉnh của đồ thị
int m;//số cạnh của đồ thị.
int sc;//số cạnh của cây khung nhỏ nhất.
int w;//Độ dài của cây khung nhỏ nhất.
int chuaxet[100];//mảng đánh dấu danh sách đỉnh đã thêm vào cây khung nhỏ nhất.
int cck[100][3];//danh sách cạnh của cây khung nhỏ nhất.
void nhap(void){
 int i, j, k;
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh: "<<n<<endl;
 cout<<"So canh: "<<m<<endl;
 //khỏi tạo ma trận trọng số của đồ thị a[i][j] = MAX.
 for (i = 1; i <= n; i++){
  chuaxet[i] = TRUE;//Gán nhãn cho các đỉnh.
  for (j = 1; j <= n; j++)
   a[i][j] = MAX;
 }

 //nhập danh sách cạnh.
 for (int p = 1; p <= m; p++){
  cin>>i>>j>>k;
  a[i][j] = k;
  a[j][i] = k;
 }
}
void PRIM(void){
 int k, top, min, l, t, u;
 int s[100];//mảng chứa các đỉnh của cây khung nhỏ nhất.
 sc = 0; w = 0; u = 1;
 top = 1;
 s[top] = u;// thêm đỉnh u bất kỳ vào mảng s[]
 chuaxet[u] = FALSE;
 while (sc<n - 1) {
  min = MAX;
  //tìm cạnh có độ dài nhỏ nhất với các đỉnh trong mảng s[].
  for (int i = 1; i <= top; i++){
   t = s[i];
   for (int j = 1; j <= n; j++){
    if (chuaxet[j] && min>a[t][j]){
     min = a[t][j];
     k = t;
     l = j;
    }
   }
  }
  sc++;
  w = w + min;
  //thêm vào danh sách cạnh của cây khung.
  cck[sc][1] = k;
  cck[sc][2] = l;
  chuaxet[l] = FALSE; 
  top++;
  s[top] = l;
 }
}
void Result(void){
 cout<<"Do dai ngan nhat:"<< w<<endl;
 cout<<"Cac canh cua cay khung nho nhat"<<endl;
 for (int i = 1; i <= sc; i++)
  cout<< cck[i][1]<<" "<< cck[i][2]<<endl;
}
void main(void){
 nhap(); 
 PRIM();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
1 3
3 5
5 4
4 6
3 2

Bài tập ứng dùng bạn có thể xem thêm tại đây

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây.
Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau:
1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
2.  Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T trước đó;
3.  Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.
Thuật toán được mô tả thông qua thủ tục Kruskal như sau:

void  Kruskal(void){
 T = φ;
 While(| T | < (n - 1) and(E≠ φ)){
  Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;
 E: = E\ {e};
  if (T ∪{ e }: không tạo nên chu trình)
   T = T ∪{ e };
 }
 if (| T | <n - 1)
  Đồ thị không liên thông;
} 

Khối lượng tính toán nhiều nhất cảu thuật toán chính là ở bước sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài các cạnh để bổ xung vào cây khung. Đối với đồ thị cỡ m cạnh thì  cần phải thực hiện cỡ m*logm phép toán để sắp xếp. Tuy nhiên, để xây dựng cây khung nhỏ nhất với n-1 cạnh, ta không cần sắp xếp toàn bộ mà chỉ cần xét phần trên cảu dãy đó. Để làm việc đó ta có thể sử dụng các thủ tục sắp xếp vun đống (Heap sort).
Trong thuật toán Kruskal việc lựa chọn cạnh để bổ xung đòi hỏi phải có một thủ tục hiệu quả đế kiểm tra tập cạnh T ∪ { e } có chứa chu trình hay không. Chú ý, các cạnh trong T ở bước lặp trung gian sẽ tạo thành một rừng. Cạnh e cần khảo sát sẽ tạo thành chu trình với các cạnh trong T khi và chỉ khi cả hai đỉnh đầu của nó thuộc cùng một cây con trong rừng nói trên. Do đó thêm cạnh e vào T không tạo thành chu trình khi và chỉ khi nó phải nối 2 cây khác nhau trong T. Một trong những phương pháp hiệu quả để thực hiện việc kiểm tra này là phân hoạch các đỉnh của đồ thị thành các tập con không giao nhau. Chẳng hạn với đồ thị sau.

Tìm cây khung nhỏ nhất với thuật toán Kruskal

Ta có tập con có 6 tập con 1 phần tử: {1},{2},{3},{4},{5},{6}. Sau khi bổ xung cạnh có độ dài nhỏ nhất {3,5} ta có các tập con : {1},{2},{3,5},{4},{6}. Tiếp theo ta thêm cạnh {4,6} ta được các tập con {1},{2},{3,5},{4,6}. Tiếp theo ta thêm canh {4,5} ta được các tập con {1},{2},{3,5,4,6}. Cạnh có độ dài tiếp theo là {5,6} nhưng do hai đầu của nó thuộc cùng một tập con {3,5,4,6} nên cạnh {5,6} không được chọn.
Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 50 
#define TRUE 1 
#define FALSE  0 
int n, m, minl, connect;
int dau[500], cuoi[500], w[500];//mảng chứa đỉnh đầu, cuối và độ dài các cạnh của đồ thị.
int daut[50], cuoit[50], father[50];
void Init(void){
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh do thi: "<< n <<endl;
 cout<<"So canh do thi:" << m <<endl;
 //nhập danh sách kề
 for (int i = 1; i <= m; i++){
  cin>>dau[i]>>cuoi[i]>>w[i];
 }
}
void Heap(int First, int Last){
 int j, k, t1, t2, t3;
 j = First;
 while (j <= (Last / 2)){
  if ((2 * j) < Last && w[2 * j + 1] < w[2 * j])
   k = 2 * j + 1;
  else
   k = 2 * j;
  if (w[k] < w[j]){
   t1 = dau[j];
   t2 = cuoi[j];
   t3 = w[j];
   dau[j] = dau[k];
   cuoi[j] = cuoi[k];
   w[j] = w[k];
   dau[k] = t1;
   cuoi[k] = t2;
   w[k] = t3;
   j = k;
  }
  else j = Last;
 }
}
int Find(int i){
 int tro = i;
 while (father[tro] > 0)
  tro = father[tro];
 return(tro);
}
void Union(int i, int j){
 int x = father[i] + father[j];
 if (father[i] > father[j]) {
  father[i] = j;
  father[j] = x;
 }
 else {
  father[j] = i;
  father[i] = x;
 }
}
void Krusal(void){
 int last, u, v, r1, r2, ncanh, ndinh;
 for (int i = 1; i <= n; i++)
  father[i] = -1;
 //sử dụng thuật toán vun đống để sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài.
 for (int i = m / 2; i > 0; i--)
  Heap(i, m);

 last = m; ncanh = 0; ndinh = 0; minl = 0; connect = TRUE;
 //Lựa chọn cạnh bổ xung vào cây khung.
 while (ndinh < n - 1 && ncanh < m){
  ncanh = ncanh + 1;
  u = dau[1];
  v = cuoi[1];
  //tìm gốc của phân hoạch 1.
  r1 = Find(u);
  //tìm gốc của phân hoạch 2.
  r2 = Find(v);
  if (r1 != r2) {//nếu hai gốc khác nhau thì cạnh đang xét có thể thêm được vào đồ thị.
   ndinh = ndinh + 1;
   Union(r1, r2);
   daut[ndinh] = u;
   cuoit[ndinh] = v;
   minl = minl + w[1];
  }
  dau[1] = dau[last];
  cuoi[1] = cuoi[last];
  w[1] = w[last];
  last = last - 1;
  Heap(1, last);
 }
 if (ndinh != n - 1) connect = FALSE;
}
void Result(void){
 cout<<"Do dai cay khung nho nhat:"<< minl<<endl;
 cout<<"Cac canh cua cay khung nho nhat:"<<endl;
 for (int i = 1; i < n; i++)
  cout<< daut[i]<<" "<<cuoit[i]<<endl;
}
void main(void){
 Init();
 Krusal();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
3 5
4 6
4 5
1 3
2 3

Bài tập ứng dùng bạn có thể xem thêm tại đây

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây.
Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau:
1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
2.  Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T trước đó;
3.  Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.
Thuật toán được mô tả thông qua thủ tục Kruskal như sau:

void  Kruskal(void){
 T = φ;
 While(| T | < (n - 1) and(E≠ φ)){
  Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;
 E: = E\ {e};
  if (T ∪{ e }: không tạo nên chu trình)
   T = T ∪{ e };
 }
 if (| T | <n - 1)
  Đồ thị không liên thông;
} 

Khối lượng tính toán nhiều nhất cảu thuật toán chính là ở bước sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài các cạnh để bổ xung vào cây khung. Đối với đồ thị cỡ m cạnh thì  cần phải thực hiện cỡ m*logm phép toán để sắp xếp. Tuy nhiên, để xây dựng cây khung nhỏ nhất với n-1 cạnh, ta không cần sắp xếp toàn bộ mà chỉ cần xét phần trên cảu dãy đó. Để làm việc đó ta có thể sử dụng các thủ tục sắp xếp vun đống (Heap sort).
Trong thuật toán Kruskal việc lựa chọn cạnh để bổ xung đòi hỏi phải có một thủ tục hiệu quả đế kiểm tra tập cạnh T ∪ { e } có chứa chu trình hay không. Chú ý, các cạnh trong T ở bước lặp trung gian sẽ tạo thành một rừng. Cạnh e cần khảo sát sẽ tạo thành chu trình với các cạnh trong T khi và chỉ khi cả hai đỉnh đầu của nó thuộc cùng một cây con trong rừng nói trên. Do đó thêm cạnh e vào T không tạo thành chu trình khi và chỉ khi nó phải nối 2 cây khác nhau trong T. Một trong những phương pháp hiệu quả để thực hiện việc kiểm tra này là phân hoạch các đỉnh của đồ thị thành các tập con không giao nhau. Chẳng hạn với đồ thị sau.

Tìm cây khung nhỏ nhất với thuật toán Kruskal

Ta có tập con có 6 tập con 1 phần tử: {1},{2},{3},{4},{5},{6}. Sau khi bổ xung cạnh có độ dài nhỏ nhất {3,5} ta có các tập con : {1},{2},{3,5},{4},{6}. Tiếp theo ta thêm cạnh {4,6} ta được các tập con {1},{2},{3,5},{4,6}. Tiếp theo ta thêm canh {4,5} ta được các tập con {1},{2},{3,5,4,6}. Cạnh có độ dài tiếp theo là {5,6} nhưng do hai đầu của nó thuộc cùng một tập con {3,5,4,6} nên cạnh {5,6} không được chọn.
Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 50 
#define TRUE 1 
#define FALSE  0 
int n, m, minl, connect;
int dau[500], cuoi[500], w[500];//mảng chứa đỉnh đầu, cuối và độ dài các cạnh của đồ thị.
int daut[50], cuoit[50], father[50];
void Init(void){
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh do thi: "<< n <<endl;
 cout<<"So canh do thi:" << m <<endl;
 //nhập danh sách kề
 for (int i = 1; i <= m; i++){
  cin>>dau[i]>>cuoi[i]>>w[i];
 }
}
void Heap(int First, int Last){
 int j, k, t1, t2, t3;
 j = First;
 while (j <= (Last / 2)){
  if ((2 * j) < Last && w[2 * j + 1] < w[2 * j])
   k = 2 * j + 1;
  else
   k = 2 * j;
  if (w[k] < w[j]){
   t1 = dau[j];
   t2 = cuoi[j];
   t3 = w[j];
   dau[j] = dau[k];
   cuoi[j] = cuoi[k];
   w[j] = w[k];
   dau[k] = t1;
   cuoi[k] = t2;
   w[k] = t3;
   j = k;
  }
  else j = Last;
 }
}
int Find(int i){
 int tro = i;
 while (father[tro] > 0)
  tro = father[tro];
 return(tro);
}
void Union(int i, int j){
 int x = father[i] + father[j];
 if (father[i] > father[j]) {
  father[i] = j;
  father[j] = x;
 }
 else {
  father[j] = i;
  father[i] = x;
 }
}
void Krusal(void){
 int last, u, v, r1, r2, ncanh, ndinh;
 for (int i = 1; i <= n; i++)
  father[i] = -1;
 //sử dụng thuật toán vun đống để sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài.
 for (int i = m / 2; i > 0; i--)
  Heap(i, m);

 last = m; ncanh = 0; ndinh = 0; minl = 0; connect = TRUE;
 //Lựa chọn cạnh bổ xung vào cây khung.
 while (ndinh < n - 1 && ncanh < m){
  ncanh = ncanh + 1;
  u = dau[1];
  v = cuoi[1];
  //tìm gốc của phân hoạch 1.
  r1 = Find(u);
  //tìm gốc của phân hoạch 2.
  r2 = Find(v);
  if (r1 != r2) {//nếu hai gốc khác nhau thì cạnh đang xét có thể thêm được vào đồ thị.
   ndinh = ndinh + 1;
   Union(r1, r2);
   daut[ndinh] = u;
   cuoit[ndinh] = v;
   minl = minl + w[1];
  }
  dau[1] = dau[last];
  cuoi[1] = cuoi[last];
  w[1] = w[last];
  last = last - 1;
  Heap(1, last);
 }
 if (ndinh != n - 1) connect = FALSE;
}
void Result(void){
 cout<<"Do dai cay khung nho nhat:"<< minl<<endl;
 cout<<"Cac canh cua cay khung nho nhat:"<<endl;
 for (int i = 1; i < n; i++)
  cout<< daut[i]<<" "<<cuoit[i]<<endl;
}
void main(void){
 Init();
 Krusal();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
3 5
4 6
4 5
1 3
2 3

Bài tập ứng dùng bạn có thể xem thêm tại đây