Untitled
unknown
plain_text
a year ago
3.0 kB
3
Indexable
#include<iostream> using namespace std; int nt; // Số lượng bộ test int n, m; // Số đỉnh và số cạnh trong đồ thị int map[21][21]; // Ma trận lưu trữ đồ thị int dem[21]; // Mảng đếm số lần đi qua mỗi đỉnh int vx, vy; // Biến tạm thời lưu giá trị các đỉnh trong cạnh // Khởi tạo lại ma trận đồ thị void restmap() { for(int i = 0; i <= n; i ++) { for(int j = 0; j <= n; j++) { map[i][j]= 0; } } } // Khởi tạo lại mảng đếm số lần đi qua đỉnh void resetDem() { for(int i =0 ; i <= n; i++) { dem[i]=0; } } // Đếm số lượng đỉnh khác nhau đã đi qua int countdiem() { int len = 0; for(int i = 1; i <= n; i++) { if(dem[i]!=0) { len++; } } return len; } // Thuật toán Backtracking để tìm đường đi tối ưu void Backtrack(int v) { // Nếu đến được đích và số đỉnh 1 và 2 đều được đi qua đúng số lần if(v==1 && dem[1]==2 && dem[2]==1) { // Đếm số lượng đỉnh khác nhau đã đi qua và cập nhật vào mindiem int len = countdiem(); if(len < mindiem) { mindiem = len; } return; } // Nếu số đỉnh khác nhau đã đi qua lớn hơn mindiem, dừng lại if(countdiem() > mindiem) { return; } // Thử tất cả các cách di chuyển từ đỉnh hiện tại v for(int i = 1; i <= n; i++) { // Nếu có đường đi từ v đến i và số lần đi qua đỉnh i chưa đạt tối đa if(map[v][i] == 1 && ((dem[2]==1 && dem[i] < 2) || (dem[2]==0 && dem[i]<1))) { // Đánh dấu đã đi qua đỉnh i dem[i]++; // Thử di chuyển đến đỉnh i Backtrack(i); // Quay lui: bỏ đánh dấu đã đi qua đỉnh i dem[i]--; } } } int main() { // Đọc số lượng bộ test cin >> nt; for(int test = 1; test <= nt; test++) { // Đọc số đỉnh và số cạnh của đồ thị cin >> n >> m; // Khởi tạo lại ma trận đồ thị và mảng đếm số lần đi qua đỉnh restmap(); resetDem(); // Đọc các cạnh của đồ thị và lưu vào ma trận đồ thị for(int i = 0; i < m; i++) { cin >> vx >> vy; map[vx][vy] = 1; } // Khởi tạo biến mindiem với giá trị lớn để lưu số đỉnh tối thiểu cần đi qua mindiem = 9999999; // Bắt đầu thử tất cả các đường đi có thể từ đỉnh 1 dem[1] = 1; Backtrack(1); // In ra màn hình số đỉnh tối thiểu cần đi qua từ đỉnh 1 đến đỉnh 2 và quay lại đỉnh 1 cout << mindiem << endl; } return 0; }
Editor is loading...
Leave a Comment