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

}

[Bài tập mẫu] Đa giác số

Bài toán: Trên vòng tròn đánh dấu n điểm phân biệt. Các điểm này được chọn làm n đỉnh của đa giác lồi P. Vẽ tất cả các đường chéo của đa giác P. Cho N là một họ gồm n số nguyên dương. Mỗi số của họ N sẽ được viết bên cạnh một đỉnh của đa giác P. Ta gọi việc làm này là phân bố các số của họ N cho các đỉnh của đa giác P. Tiếp theo, mỗi đường chéo của đa giác P sẽ được gán cho một số nguyên bằng tích của hai số gán cho đỉnh đầu mút của nó.
Ví dụ: n = 7, N = <15, 12, 2, 12, 10, 11, 10>. Một cách phân bố các số của họ N cho các đỉnh của đa giác được chỉ ra trong hình vẽ dưới đây:

Yêu cầu: Tìm cách phân bố các số của họ N cho các đỉnh của đa giác sao cho tổng các số gán cho các đường chéo là lớn nhất.
Dữ liệu: Vào từ file văn bản NUMPOLY.INP:

• Dòng đầu tiên chứa số nguyên n (3 < n ≤ 105).
• Dòng thứ hai chứa n số nguyên dương của họ N, mỗi số không vượt quá 106, hai số liên tiếp phân tách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản NUMPOLY.OUT 5 chữ số cuối cùng của tổng các số gán trên đường chéo theo cách phân bố tìm được. Chú ý là file kết quả phải chứa đúng 5 chữ số (như vậy, số gồm 5 chữ số trên file kết quả có thể có các số 0 đứng đầu).

NUMPOLY.INP	NUMPOLY.OUT
7 15 12 2 12 10 11 10	01487

Giải thích: Cách phân bố cho trong hình vẽ minh họa ở trên có tổng các số gán cho đường chéo là số có tận cùng bởi 5 chữ số ‘01487’.

Phát biểu lại bài toán:

• Cho N số nguyên: a0, a1,…, an-1 (3 < n ≤10^5);
• Tìm cách phân bố n số cho các đỉnh của đa giác n đỉnh sao cho tổng các số gán cho các đường chéo ( bằng tích của hai số ở hai đỉnh đầu mút) là lớn nhất.

Giải thuật

• Ta có khai triển: (SUM(ai))^2 = SUM((ai)^2) + 2* SUM(ai*a(i+1)mod n) + 2* SUM(ai*aj); trong đó  i = 0 to n-1
• Ta tính được bình phương tổng của các số (ký hiệu là ∑) và tổng các bình phương của các số S1, nên nếu ký hiệu S2 là tổng của tích các cặp số liên tiếp thì tổng các số trên đường chéo S được tính bởi công thức sau: S = (∑ - S1 – 2S2)/2.
• Từ đó suy ra bài toán dẫn về tìm cực tiểu tổng S1.
• Nhận xét này cho phép giảm độ phức tạp, bởi vì số lượng đường chéo là n(n-3)/2, trong đó n là số đỉnh của đa giác.
• Hơn nữa, ta có thuật toán đơn giản đê tìm cấu hình cho cực tiểu tổng S1: Sắp xếp các số a1, sau đó bắt đầu từ hai đầu dãy, tiến hành hoán đổi các số và dịch chuyển sang bên cạnh: phái trái dịch từ trái sang phải, phái phải dịch từ phải sang trái cho đến khi chờm qua nhau. Khi phân bố chú ý tiến hành tính chỉ số theo model.

Chương trình cài đặt:

#include <cstdio>
#include <iostream>
#include<stdlib.h>
#include<conio.h>
using namespace std;
#define nmax 1000000
int array[nmax];
unsigned long long sum;
unsigned long long SIGMA, sigma, sumS1;
int compare(const void * a, const void * b)
{
 return (*(int*)a - *(int*)b);
}
int main(int argc, char** argv)
{
 freopen("NUMPOLY.INP", "r", stdin);
 freopen("NUMPOLY.OUT", "w", stdout);


 int n;
 cin >> n;
 for (int i = 0; i < n; i++){
  cin>> array[i];
  SIGMA += array[i];
  sigma += array[i] * array[i];
 }
 SIGMA *= SIGMA;
 qsort(array, n, sizeof(int), compare);
 
 for (int i = 1; i < n/2; i = i+ 2){
  int temp = array[i];
  array[i] = array[n - 1 - i];
  array[n - 1 - i] = temp;
 }
 for (int i = 0; i < n; i ++){
  sumS1 += (unsigned long long) array[i] * array[(i + 1) % n];
 }

 sum = (unsigned long long)(SIGMA - sigma - 2 * sumS1) / 2;
 if (sum < 10){
  cout << "0000" << sum;
 }
 else if (sum < 100){
  cout << "000" << sum;
 }
 else if (sum < 1000){
  cout << "00" << sum;
 }
 else if (sum < 10000){
  cout << "0" << sum;
 }
 else{
  cout<< sum%100000;
 }
 
 return 0;
}

[Bài tập mẫu] Con đường Tùng - Trúc.

[Bài toán] Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng,dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất a cây tùng và có ít nhất b cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả n cây, không có hai cây nào ở cùng một vị trí. Cây thứ i ở vị trí có khoảng cách đến vị trí bắt đầu con đường là di (i = 1, 2, …, n). Với kinh phí có hạn, Ban quản lý muốn chọn đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.
Yêu cầu: Cho a, b và vị trí của n cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đó có ít nhất a cây tùng và có ít nhất b cây trúc.
Dữ liệu: Vào từ file văn bản MINROAD.INP:
* Dòng đầu chứa 3 số nguyên dương n, a, b (a + b ≤ n);
* Dòng thứ i trong n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương di (di ≤ 109) và ki, trong đó di là khoảng cách của cây tính từ vị trí bắt đầu của con đường, ki = 1 nếu là cây tùng, ki = 2 nếu là cây trúc.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản MINROAD.OUT một số nguyên là độ dài đoạn đường ngắn nhất tìm
được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.
[Input example]
7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1
[Output example]
35
[Giải thuật]
* Sắp xếp dãy vị trí của các cây theo thứ tự tăng dần: d[1] < d[2] <...
* Bắt đầu từ đầu dãy, duyệt từ trái qua phải để tìm các đoạn gồm dãy các phần tử liên tiếp chứa ít nhất a cây tùng và ít nhất b cây trúc. Mỗi lần tìm được đoạn như vậy ghi nhận độ dài để tìm ra đoạn ngắn nhất.

#include <cstdio>
#include <iostream>
#include<stdlib.h>
using namespace std;
#define nmax 300000
long data[nmax][2];
int compare(const void *arg1, const void *arg2)
{
 int const *lhs = static_cast<int const*>(arg1);
 int const *rhs = static_cast<int const*>(arg2);
 return (lhs[0] < rhs[0]) ? -1
  : ((rhs[0] < lhs[0]) ? 1
  : (lhs[1] < rhs[1] ? -1
  : ((rhs[1] < lhs[1] ? 1 : 0))));
};
int main(int argc, char** argv)
{
 freopen("MINROAD.INP", "r", stdin);
 freopen("MINROAD.OUT", "w", stdout);

 int n, a, b;
 scanf("%d %d %d", &n, &a, &b);
 if (a == 0 && b == 0){
  printf("%d", -1);
  return 0;
 }
 for (int i = 0; i < n; i++)
  scanf("%d %d", &data[i][0], &data[i][1]);

 qsort(data, n, 2 * sizeof(int), compare);

 long min = 1000000000;
 int head, tail = 0;
 int countTung = 0;
 int countTruc = 0;

 for (int i = 0; i < n; i++){
  if (data[i][1] == 1){
   countTung++;
  }
  else{
   countTruc++;
  }
  if (countTung >= a && countTruc >= b){
   head = i;
   min = data[head][0] - data[tail][0];
   break;
  }
 }

 bool isSub = false;
 while (head < n){ 
  for (int j = tail; j < head; j++){
   isSub = false;
   if (data[j][1] == 1 && countTung >a){
    countTung --;
    tail += 1;
    isSub = true;
   }
   if (data[j][1] !=1 && countTruc >b){
    countTruc--;
    tail += 1;
    isSub = true;
   }
   if(!isSub) break;
   if (data[head][0] - data[tail][0] < min){
     min = data[head][0] - data[tail][0];
    }

  }
  head++;
  if (head < n){
   if (data[head][1] == 1){
    countTung++;
   }
   else{
    countTruc++;
   }
  }
 }
 if (min == 1000000000){ min = -1; }
 printf("%d", min);
 return 0;
}

[Bài toán] Xếp hậu

Bài toán:  Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau bằng thuật toán Back Track.
Giải. Bàn cờ có n hàng được đánh số từ 0 đến n-1, n cột được đánh số từ 0 đến n-1; Bàn cờ có n*2 -1 đường chéo xuôi được đánh số từ 0 đến 2*n -2, 2 *n -1 đường chéo ngược được đánh số từ 2*n -2. Ví dụ: với bàn cờ 8 x 8, chúng ta có 8 hàng được đánh số từ 0 đến 7, 8 cột được đánh số từ 0 đến 7, 15 đường chéo xuôi, 15 đường chéo ngược được đánh số từ 0..15.
     Vì trên mỗi hàng chỉ xếp được đúng một quân hậu, nên chúng ta chỉ cần quan tâm đến quân hậu được xếp ở cột nào. Từ đó dẫn đến việc xác định bộn thành phần x1, x2,.., xn, trong đó xi= j được hiểu là quân hậu tại dòng i xếp vào cột thứ j. Giá trị của i được nhận từ 0 đến n-1; giá trị của j cũng được nhận từ 0 đến n-1, nhưng thoả mãn điều kiện ô (i,j) chưa bị quân hậu khác chiếu đến theo cột, đường chéo xuôi, đường chéo ngược.
     Việc kiểm soát theo hàng ngang là không cần thiết vì trên mỗi hàng chỉ xếp đúng một quân hậu. Việc kiểm soát theo cột được ghi nhận nhờ dãy biến logic aj với qui ước aj=1 nếu cột j còn trống, cột aj=0 nếu cột j không còn trống. Để ghi nhận đường chéo xuôi và đường chéo ngược có chiếu tới ô (i,j) hay không, ta sử dụng phương trình i + j = const và i - j = const, đường chéo thứnhất được ghi nhận bởi dãy biến bj, đường chéo thứ 2 được ghi nhận bởi dãy biến cj với qui ước nếu đường chéo nào còn trống thì giá trị tương ứng của nó là 1 ngược lại là 0. Như vậy, cột j được chấp nhận khi cả 3 biến aj, bi+j, ci+j đều có giá trị 1. Các biến này phải được khởi đầu giá trị 1 trước đó, gán lại giá trị 0 khi xếp xong quân hậu thứ i và trả lại giá trị 1 khi đưa ra kết quả.

#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <dos.h> 
#define N  8 
#define D  (2*N-1) 
#define SG  (N-1) 
#define TRUE 1 
#define FALSE 0 
void hoanghau(int);
void inloigiai(int  loigiai[]); FILE *fp;
int  A[N], B[D], C[D], loigiai[N];
int soloigiai = 0;
void hoanghau(int i){
 int j;
 for (j = 0; j < N; j++){
  if (A[j] && B[i - j + SG] && C[i + j]) {
   loigiai[i] = j;
   A[j] = FALSE;
   B[i - j + SG] = FALSE;
   C[i + j] = FALSE;
   if (i == N - 1){
    soloigiai++;
    inloigiai(loigiai);
    delay(500);
   }
   else
    hoanghau(i + 1);
   A[j] = TRUE;
   B[i - j + SG] = TRUE;
   C[i + j] = TRUE;
  }
 }
}
void inloigiai(int *loigiai){
 int j;
 printf("\n Lời giải %3d:", soloigiai);
 fprintf(fp, "\n Lời giải %3d:", soloigiai);
 for (j = 0; j < N; j++){
  printf("%3d", loigiai[j]);
  fprintf(fp, "%3d", loigiai[j]);
 }
}
void main(void){
 int i; clrscr();
 fp = fopen("loigiai.txt", "w");
 for (i = 0; i < N; i++)
  A[i] = TRUE;
 for (i = 0; i < D; i++){
  B[i] = TRUE;
  C[i] = TRUE;
 }
 hoanghau(0);
 fclose(fp);
}

Dưới đây là số cách xếp hậu ứng với n.

n	4	7	8	9	10	11	12	13	14
Hn	2	40	92	352	724	2680	14200	73712	365596

Nghiệm đầu tiên mà chương trình tìm được ứng với n =8 là x =(1, 5, 8, 6, 3, 7, 2, 4).

[Bài toán] Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

     Biểu diễn hoán vị dưới dạng p1, p2,.., pn, trong đó pi nhận giá trị từ 1 đến n và pi≠pj với i≠j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy, cần phải ghi nhớ với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy các biến logic bj, trong đó bj= true nếu j chưa được dùng. Các biến này phải được khởi đầu giá trị true trong thủ tục Init. Sau khi gán j cho pi, cần ghi nhận false cho bj và phải gán true khi thực hiện xong Result hay Try(i+1). Hình sau mô tả cây tìm kiếm lời giải bài toán liệt kê hoán vị của 1, 2,.., n với n = 3.

Chương trình cài đặt.

#include  <stdio.h> 
#include  <conio.h> 
#include  <stdlib.h> 
#define MAX 100 
#define TRUE 1 
#define FALSE 0 
int P[MAX], B[MAX], n, count = 0;
void Init(void){
 int i;
 printf("\n Nhap n="); scanf("%d", &n);
 for (i = 1; i <= n; i++)
  B[i] = TRUE;
}
void Result(void){
 int i; count++;
 printf("\n Hoan vi thu %d:", count);
 for (i = 1; i <= n; i++)
  printf("%3d", P[i]);
 getch();
}
void Try(int i){
 int j;
 for (j = 1; j <= n; j++){
  if (B[j]) {
   P[i] = j;
   B[j] = FALSE;
   if (i == n) Result();
   else Try(i + 1);
   B[j] = TRUE;
  }
 }
}
void main(void){
 Init();
 Try(1);
}

[Bài toán] Liệt kê các tập con k phần tử của tập n phần tử bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.
     Biểu diễn tập con k phần tử dưới dạng c1, c2,.., ck, trong đó 1< c1các giá trị đề cử cho ci là từ ci-1+ 1 cho đến n - k + i. Cần thêm vào c0= 0. Các giá trị đề cử này
mặc nhiên được chấp nhận mà không cần phải thêm điều kiện gì. 

Chương trình cài đặt:

#include <conio.h> 
#include <stdio.h> 
#include <stdlib.h> 
#define MAX  100 
int B[MAX], n, k, count = 0;
void Init(void){
 printf("\n Nhap n="); scanf("%d", &n);
 printf("\n Nhap k="); scanf("%d", &k);
 B[0] = 0;
}
void Result(void){
 int i; count++;
 printf("\n Tap thu %d:", count);
 for (i = 1; i <= k; i++){
  printf("%3d", B[i]);
 }
 getch();
}
void Try(int i){
 int j;
 for (j = B[i - 1] + 1; j <= (n - k + i); j++){
  B[i] = j;
  if (i == k) Result();
  else Try(i + 1);
 }
}
void main(void){
 clrscr();
 Init();
 Try(1);
}