Đường đi dài nhất từ thành phố D đến thành phố C
Có n thành phố biết rằng đường đi giữa các thành phố là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận A[i,j] trong đó:
- A[i,j] là độ dài đường đi từ thành phố i đến thành phố j.
- A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
- A[i,j] = A[j,i]
- A[i,j] nguyên, không âm.
Hãy xác định đường đi dài nhất từ thành phố D đến thành phố C với điều kiện thành phố đã qua không được đi lại.
Dữ liệu vào:đồ thị đã liên thông và cho trong file Bai10.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0< n <100)
- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (1<= i <=n) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: xuất ra màn hình đường đi dài nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.
INPUT 1
6
1 6
0 1 2 0 0 0
1 0 2 2 3 0
2 2 0 5 4 0
0 2 5 0 3 2
0 3 4 3 0 4
0 0 0 2 4 0
OUTPUT 1
DUONG DI DAI NHAT LA: 16
1->2->4->3->5->6
INPUT 2
6
1 6
0 1 4 0 0 0
1 0 2 6 5 0
4 2 0 7 3 0
0 6 7 0 0 1
0 5 3 0 0 3
0 0 0 1 3 0
OUTPUT 2
DUONG DI DAI NHAT LA: 25
1->3->4->2->5->6
HƯỚNG DẪN CÀI ĐẶT
Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy, khi tìm được 1 phương án thì lưu lại trạng thái của phương án ban đầu và so sánh với phương án mới tìm được, nếu phương án mới tốt hơn thì chọn phương án mới.
Code:
include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Input.inp"
/*Khai báo các biến toàn cục*/
int*L,*L1; //Luu lai duong da di
char*DanhDau; //Danh dau dinh da di
int **A,n,D,C,Tong,Tong1,Canh1;
/*Dọc file dữ liệu của bài toán*/
void Doc_File() {
FILE*f = fopen(Filename,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--; C--;
}
/*Khởi tạo ban đầu cho thủ tục tìm kiếm*/
void KhoiTao() {
DanhDau = new char [n];
L = new int [n]; //Lưu đường đi tìm được
L1 = new int [n]; //Lưu đường đi lớn nhất
for (int i = 0; i<n; i++) {
DanhDau[i] = 0; //Các đỉnh chưa được đánh dấu
L[i] = 0;
}
DanhDau[D] = 1; //Dánh dấu đỉnh xuẩt phát
L[0] = D; //Đường đi đầu tiên qua đỉnh đầu
Tong = 0; //Trong số đường đi
Tong1 = 0; //Lưu lại trọng số lớn nhất của đường đi
}
/*In đường đi dài nhất tìm được*/
void InDuongDi() {
cout<<"\nDUONG DI DAI NHAT:"<<Tong1<<endl<<D+1;
for (int i = 1; i<Canh1; i++)
cout<<" -> "<<L1[i]+1;
}
/*Xử lý để lấy phương án tổt hơn*/
void XuLy(int Canh) {
if(Tong>Tong1){
Tong1 = Tong; //Lưu lại trọng số tốt hơn
Canh1 = Canh; //Lưu lại số cạnh đã đi qua
for(int i =0; i<Canh; i++)
L1[i] = L[i]; //Lưu lại đường đi tốt hơn
}
}
/*Thủ tục tìm kiếm đệ quy*/
void TimKiem(int SoCanh) {
if(L[SoCanh-1] == C) XuLy(SoCanh);
else { for(int i = 0; i<n; i++)
if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0){
L[SoCanh] = i;
DanhDau[i] = 1;
Tong+=A[L[SoCanh-1]][i];
TimKiem(SoCanh+1);
L[SoCanh] = 0;
Tong-=A[L[SoCanh-1]][i];
DanhDau[i] = 0;
}
}
}
void main() {
Doc_File();
KhoiTao();
TimKiem(1);
if(Tong1==0) cout<<"\NKHONG CO DUONG DI";
else InDuongDi();
delete*A,DanhDau,L;
getch();
}
Được sửa bởi Admin ngày Thu May 26, 2011 8:33 am; sửa lần 2.
