Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
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

Shopmotion


Affiliates
free forum


Đường đi dài nhất từ thành phố D đến thành phố C

View previous topic View next topic Go down

Đường đi dài nhất từ thành phố D đến thành phố C

Post  Admin on Wed Jun 15, 2011 10:40 pm

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();
}

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum