Search
Latest topics
Đường đi dài nhất từ thành phố D đến thành phố C
Page 1 of 1
Đường đi dài nhất từ thành phố D đến thành phố C
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.
- 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();
}
Similar topics
» cho địa chỉ đường mang 192.168.1.0. hãy cho biết dùng subnet mask nào khi chia subnet để được ít nhất 5 mạng con và nhiều nhất 30 địa chỉ IP trong môix mạng con đó?
» Khử đệ quy bài toán tìm mọi đường đi từ thành phố D đến C
» Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
» Hàm vẽ đường thẳng và eclipse c/c++ .net
» Ứng dụng đường đi Hamilton
» Khử đệ quy bài toán tìm mọi đường đi từ thành phố D đến C
» Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
» Hàm vẽ đường thẳng và eclipse c/c++ .net
» Ứng dụng đường đi Hamilton
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
Thu Aug 23, 2012 5:38 am by Admin
» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin
» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin
» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin
» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin
» Giá của món quà
Fri Apr 13, 2012 6:01 am by Admin
» Sẽ chỉ yêu ai?
Fri Apr 13, 2012 6:01 am by Admin
» Cách đọc bảng chữ cái!
Thu Apr 12, 2012 10:37 pm by Admin
» Gắn trojan, keylog, virus vào website, forum
Tue Apr 10, 2012 1:14 am by Admin