Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị

Chuyên đề: ĐƯỜNG ĐI NGẮN NHẤT

1. Bin Laden

Mã bài: BINLADEN

Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không hắn thoát mất.

• 
  Dòng 1 ghi M và N
  
• 
  Dòng 2 đến 2M + 1, dòng chẵn ghi N số, dòng lẻ ghi N - 1 số là chi phí để phá cửa.
  

Ghi ra 1 số là thời gian nhỏ nhất để đến được phòng của Bin Laden

• 
  1 <= M <= 2222
  
• 
  1 <= N <= 10
  
• 
  Chi phí của các cánh cửa thuộc [0, 1000].
  

2. Xúc xắc

Mã bài: XUCXAC

Cho 1 con xúc xắc nằm vừa vặn trên một ô của lưới. Mỗi mặt của xúc xắc là một số từ 1 đến 6. Ban đầu, mặt trước là số 1, mặt trên là số 2 và mặt bên phải là số 3, các mặt đối diện có tổng số là 7. Mỗi lần, con xúc xắc có thể lăn về phía trái, phải, trước, sau. Mỗi lần tiếp xúc với mặt bàn, ta mất một chi phí bằng số ghi trên ô mà xúc xắc đang nằm trên nhân với số trên mặt của xúc xắc đang tiếp xúc với mặt bàn.

Hãy tìm cách lăn từ một ô đến một ô khác trên mặt bàn để đạt chi phí nhỏ nhất.

Dữ liệu

• 
  Dòng đầu ghi 2 số M, N lần lượt là số dòng và số cột của lưới ô trên mặt bàn.
  
• 
  M dòng sau, mỗi dòng ghi N số nguyên không quá 100 là số ghi trên các ô lưới của mặt bàn. Các dòng được liệt kê theo thứ tự từ xa đến gần, các số trên mỗi dòng liệt kê từ trái sang phải.
  
• 
  Dòng cuối ghi 2 cặp số lần lượt là tọa độ (dòng, cột) của ô bắt đầu và ô kết thúc.
  

Kết quả

Giới hạn

Ví dụ

3. Traffic Network

Mã bài: TRAFFICN

Nhiệm vụ của bạn là viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất giữa s và t là nhỏ nhất.

Dữ liệu vào

Với mỗi bộ dữ liệu, dòng đầu tiên chứa năm số nguyên dương n (n ≤ 10 000), m (m ≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) cách nhau bởi dấu trống. Dòng thứ i trong m dòng tiếp theo chứa ba số nguyên dương di, ci, li cách nhau bởi dấu trống, trong đó li là độ dài ( 0< li ≤ 1000) của đường một chiều thứ i từ nút di đến nút ci. Dòng thứ j trong k dòng tiếp theo chứa ba số nguyên dương uj, vj và qj (qj ≤ 1000) cách nhau bởi dấu trống, trong đó qj là độ dài của đường hai chiều được đề xuất thứ j nối giữa hai nút uj và vj.

Dữ liệu ra

4. Roads

Mã bài: ROADS

Dữ liệu

Kết quả

Ví dụ

5. Vị trí tốt nhất

Mã bài: BESTSPOT

Bessie biết rằng cô ấy có thể xác định được C (1 <= C <= 8000) con đường hai chiều (được đánh số 1 .. C) kết nối tất cả các cánh đồng trong toàn bộ nông trại. Ứng với mỗi con đường P_i là thời gian đi T_i (1 <= T_i <= 892) và nối 2 cánh đồng a_i và b_i (1 <= a_i <= P; 1 <= b_i <= P).

Bessie muốn tìm cánh đồng tốt nhất để ngủ thỏa mãn bình quân thời gian để đi đến F cánh đồng yêu thích của cô ta là nhỏ nhất.

Ví dụ, hãy xem xét một nông trang được trình bày như một bản đồ dưới đây , nơi * 'd là cách đồng được yêu thích.Các số trong ngoặc là thời gian tương ứng để di chuyển giữa 2 cánh đồng .

1 *-- [4] - 2 - [2] - 3

| |

| |

| | | |

| | | |

Bảng sau đây cho thấy các khoảng cách trung bình nếu nghỉ tại các cánh đồng 4, 5, 6, 7, 9, 10, 11, và 12: 4 7 16 5 6 9 3 46/6 = 7.67 5 10 13 2 3 6 6 40/6 = 6.67 6 11 12 1 2 5 7 38/6 = 6.33 7 16 7 4 3 6 12 48/6 = 8.00 9 12 14 3 4 7 8 48/6 = 8.00 10 12 11 0 1 4 8 36/6 = 6.00 ** BEST 11 13 10 1 0 3 9 36/6 = 6.00 12 16 13 4 3 0 12 48/6 = 8.00

Kết quả tối ưu là cánh đồng 10

Dữ liệu

• 
  Dòng 1: 3 số nguyên P,F,C
  
• 
  Dòng 2..F+1: Dòng i+2 chứa 1 số Nguyên F_i
  
• 
  Dòng F+2..C+F+1 : Mỗi dòng chứa 3 số Nguyên a_i, b_i, F_i mô tả 1 con đường 2 chiều là thời gian di chuyển giữa chúng.
  

Kết quả

Ví dụ

6. Số phụ thuộc

Mã bài: SUMS

Ví dụ cho A={2,5,7}. Các số như 2, 4(2+2), 12(5+7 hoặc 2+2+2+2+2) được gọi là phụ thuộc vào tập A. Số 0 cũng gọi là phụ thuộc vào tập A.

Yêu cầu:

Dữ liệu:

• 
  Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 5000).
  
• 
  N dòng tiếp theo chứa các phân tử của tập A, a1 < a2 < ... < an (1 ≤ ai ≤ 50000 ).
  
• 
  Dòng thứ N+2 chứa số nguyên m (1 ≤ m ≤ 10000 ).
  
• 
  M dòng tiếp theo chứa dãy số nguyên b1, b2, ..., bm (0 ≤ bi ≤ 1000000000 ).
  

Kết quả:

Ví dụ:

7. CENTRE

Mã bài: CENTRE28

Tuy nhiên,cả 2 trung tâm này đều có dấu hiệu quá tải về mật độ dân số. Vì vậy, đức vua Peaceful quyết định chọn ra thêm một thành phố nữa để đầu tư thành một trung tâm kinh tế thứ ba. Thành phố này sẽ tạm ngưng mọi hoạt động thường nhật, cũng như mọi luồng lưu thông ra vào để tiến hành nâng cấp cơ sở hạ tầng. Nhưng trong thời gian sửa chữa ấy, phải bảo đảm đường đi ngắn nhất từ thành phố 1 đến thành phố N không bị thay đổi, nếu không nền kinh tế quốc gia sẽ bị trì trệ.

Vị trí và đường nối giữa N thành phố được mô tả như một đồ thị N đỉnh M cạnh. Hãy giúp nhà vua đếm số lượng thành phố có thể chọn làm trung tâm kinh tế thứ ba sao cho thành phố được chọn thỏa mãn các điều kiện ở trên

Input

Dòng thứ i trong số M dòng tiếp theo ghi 3 số nguyên dương x_i, y_i và d_i với ý nghĩa tuyến đường thứ i có độ dài d_i và nối giữa 2 thành phố x_i, y_i.

Output

S dòng tiếp theo, mỗi dòng ghi 1 số nguyên dương là số thứ tự của thành phố được chọn ( In ra theo thứ tự tăng dần )

Example

CENTRE28.INP	CENTRE28.OUT
6 6 1 2 1 2 3 1 3 6 1 1 4 100 4 5 100 5 6 100	2 4 5

Giới hạn

• 
  2 ≤ N ≤ 30000
  
• 
  1 ≤ M ≤ 100000
  
• 
  1 ≤ d_i ≤ 1000
  

8. Floyd hoặc Dijkstra ( Cơ bản )

Mã bài: FLOYD

Cho đơn đồ thị vô hướng N đỉnh và M cạnh, trọng số các cạnh đều nguyên dương. Có 2 loại câu hỏi :
0 u v : Cho biết đường đi ngắn nhất từ u tới v có độ dài là bao nhiêu.
1 u v : Hãy chỉ ra 1 đường đi ngắn nhất từ u => v
Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết 1 cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm .

Download test và solution tại đây

Input

Dòng 1 : 3 số nguyên N , M , K . ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ N*(N-1)/2 , 1 ≤ K ≤ 1000 )
M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương u , v , c cho biết cạnh (u,v) có trọng số là c ( 1 ≤ c ≤ 10000 )
K dòng tiếp theo là K câu hỏi , dòng thứ j sẽ có định dạng như đã nêu ở trên .

Output

Ứng với mỗi câu hỏi trong K câu hỏi thì ta phải trả lời trên mỗi dòng như sau .
Câu hỏi 0 u v : Ghi ra 1 số nguyên duy nhất là độ dài đường đi ngắn nhất từ u -> v.
Câu hỏi 1 u v : Ghi ra số đầu tiên là số X là số đỉnh trên đường đi ngắn nhất này , tiếp đó ghi ra X số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình .

Example

FLOYD.INP	FLOYD.OUT
3 3 2 1 2 3 2 3 1 1 3 5 0 1 2 1 1 3	3 3 1 2 3

9. Hai đường đi

Mã bài: HIWAY

Một mạng giao thông gồm N nút giao thông, và có M đường hai chiều nối một số cặp nút, thông tin về một đường gồm ba số nguyên dương u, v là tên hai nút đầu mút của đường, và l là độ dài đoạn đường đó. Biết rằng hai nút giao thông bất kì có không quá 1 đường hai chiều nhận chúng làm hai đầu mút.
Cho hai nút giao thông s và f, hãy tìm hai đường đi nối giữa s với f sao cho hai trên hai đường không có cạnh nào được đi qua hai lần và tổng độ dài 2 đường đi là nhỏ nhất.

Input

- Dòng đầu ghi N, M (N ≤ 100)
- Dòng thứ 2 ghi hai số s, f.
- M dòng tiếp theo, mỗi dòng mô tả một đường gồm ba số nguyên dương u, v, l.

Output

- Dòng đầu ghi T là tổng độ dài nhỏ nhất tìm được hoặc -1 nếu không tìm được.
- Nếu tìm được, hai dòng sau, mỗi dòng mô tả một đường đi gồm: số đầu là số nút trên đường đi này, tiếp theo là dãy các nút trên đường đi bắt đầu từ s, kết thúc tại f.

Chú ý:Phạm vi tính toán trong vòng Longint.

Example

HIWAY.INP	HIWAY.OUT
5 8 1 5 1 2 1 1 4 8 2 3 5 2 4 1 3 5 1 4 3 8 4 5 1 1 3 1	5 3 1 3 5 4 1 2 4 5

10. Vận chuyển hàng

Mã bài: QBTRANS

Công ty MCA là một công ty vận tải nổi tiếng tại đất nước Peace, với mạng lưới hoạt động trong khắp cả nước. Sắp đến kỷ niệm 30 năm thành lập, giám đốc công ty quyết định mở một đợt khuyến mãi lớn cho tất cả các khách hàng. Cụ thể là công ty sẽ mở một số tuyến đường vận chuyển miễn phí cho khách hàng.

Mỗi tuyến đường như vậy sẽ xuất phát từ một thành phố, qua một số thành phố (không đi qua thành phố nào 2 lần) rồi quay về nơi xuất phát. Nếu tính chi phí vận chuyển trung bình trên từng tuyến đường thì chi phí chi ra cho đợt khuyến mãi này sẽ không nhỏ nên giám đốc cũng muốn các tuyến đường này thỏa điều kiện tổng độ dài đường đi chia cho tổng số con đường trong tuyến đường đó (gọi là chi phí của tuyết đường) là nhỏ nhất.

Cho một mạng lưới vận chuyển hàng của công ty MCA hãy tìm ra tuyến đường thích hợp nhất (thỏa cả 2 điều kiện trên) cho đợt khuyến mãi. Xuất ra chi phí của tuyến đường tìm được.

Input

Dòng đầu tiên ghi hai số nguyên N và M là số thành phố và số con đường trong mạng lưới. ( 1 ≤ N ≤ 100, 1 ≤ M ≤ 9000 )

M dòng tiếp theo, mỗi dòng ghi ba số nguyên a b c với ý nghĩa có đường đi một chiều từ a đến b với độ dài là c. ( 1 ≤ c ≤ 2²³ )

Output

Gồm 1 dòng duy nhất ghi một số thập phân với là chi phí nhỏ nhất. Nếu không tồn tại tuyến đường nào thỏa mãn ghi ra -1. ( ghi chính xác đến 2 chữ số sau dấu phẩy )

Example

QBTRANS.INP	QBTRANS.OUT
3 3 1 2 1 2 3 1 3 1 1	1.00

11. VOI06 Kênh xung yếu

Mã bài: QBCIRARC

Một hệ thống n máy tính (các máy tính được đánh số từ 1 đến n) được nối lại thành một mạng bởi m kênh nối, mỗi kênh nối hai máy nào đó và cho phép truyền tin một chiều từ máy này đến máy kia. Ta gọi một mạch vòng của mạng đã cho là một dãy các máy tính và các kênh nối chúng có dạng:

u₁, e₁, u₂, ...,u_i, e_i, u_i+1, ..., u_k-1, e_k-1, u_k, e_k, u₁

Trong đó u₁, u₂, ..., u_k là các máy tính khác nhau trong mạng, e_i – kênh truyền tin từ máy u_i đến máy u_i+1 (i = 1, 2, ..., k-1), e_k là kênh truyền tin từ máy u_k đến máy u₁. Một kênh truyền tin trong mạng được gọi là kênh xung yếu nếu như bất cứ mạch vòng nào của mạng cũng đều chứa nó.

Yêu cầu: Hãy xác định tất cả các kênh xung yếu của mạng đã cho.

Input

Dòng đầu tiên chứa 2 số nguyên dương n và m.

Dòng thứ i trong số m dòng tiếp theo mô tả kênh nối thứ i bao gồm hai số nguyên dương u­_i, v_i cho biết kênh nối thứ i cho phép truyền tin từ máy u_i đến máy v_i.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Dòng đầu tiên ghi số nguyên k là số lượng kênh xung yếu trong mạng đã cho. Ghi k = -1 nếu mạng không chứa kênh xung yếu.

Nếu k>0 thì mỗi dòng trong số k dòng tiếp theo ghi thông tin về một kênh xung yếu tìm được theo qui cách mô tả giống như trong file dữ liệu vào. Đồng thời các kênh được in ra theo thứ tự từ điển

Example

QBCIRARC.INP	QBCIRARC.OUT
2 2 1 2 2 1	2 1 2 2 1

Hạn chế:

Trong tất cả các test: n ≤ 1000, m ≤ 20000. Có 50% số lượng test với n ≤ 200.

12. Mạng 3 đỉnh

Mã bài: THREE

Cho một đa đồ thị vô hướng N đỉnh, M cạnh, mỗi cạnh có 1 trọng số nguyên dương.

Yêu cầu: Hãy chọn ra một số cạnh sao cho đồ thị tạo bởi N đỉnh và các cạnh được chọn này đảm bảo liên thông giữa 3 đỉnh 1, 2, 3 và tổng trọng số của các cạnh được chọn là nhỏ nhất. Dữ liệu vào đảm bảo có phương án.

Giới hạn

• 
  3 ≤ N ≤ 100
  
• 
  4 ≤ M ≤ 20000
  
• 
  Trọng số 1 cạnh ≤ 10000
  

Input

• 
  Dòng đầu tiên gồm 2 số nguyên: N, M.
  
• 
  M dòng tiếp theo: dòng thứ i gồm 3 số nguyên dương U V C tương ứng là cạnh này nối liền đỉnh U với đỉnh V, trọng số là C.
  

Output

• 
  Dòng 1: Chi phí nhỏ nhất.
  
• 
  Dòng 2: Số nguyên K là số cạnh chọn ra.
  
• 
  Ghi ra K số là chỉ số các cạnh đã chọn, các số ghi cách nhau ít nhất một dấu cách.
  

Example

THREE.INP	THREE.OUT
3 4 1 2 1 2 3 4 1 3 2 1 2 3	3 2 1 3

13. Xây dựng đường

Mã bài: QBBUILD

Vua Peaceful vừa khai hoang một vùng đất để lập ra đất nước Peace, lúc đầu chỉ có N thành phố (được đánh số từ 1 đến N) và không có con đường nào.

Vua Peace chọn ra 4 thành phố đặc biệt để làm trung tâm kinh tế và 4 thành phố này phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì thế nhà vua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho 4 thành phố đặc biệt đó vẫn liên thông.

Bạn được biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn một số con đường để xây dựng để theo đúng ý nhà vua biết rằng luôn tồn tại ít nhất một phương án xây dựng đường sao cho 4 thành phố đặc biệt liên thông.

Input

Dòng đầu tiên ghi số nguyên dương N là số lượng các thành phố.( 1 ≤ N ≤ 100 )

Dòng thứ hai ghi 4 số nguyên là số hiệu của 4 thành phố đặc biệt.

Trong một số dòng tiếp theo, mỗi dòng ghi 3 số nguyên u, v và c với ý nghĩa muốn xây dựng một con đường hai chiều nối trực tiếp giữa 2 thành phố u và v thì chi phí là c. ( 1 ≤ c ≤ 5000 )

Output

Gồm 1 dòng duy nhất là tổng chi phí nhỏ nhất để xây dựng hệ thống đường.

Example

QBBUILD.INP	QBBUILD.OUT
5 2 3 4 1 1 2 10 1 5 1 5 2 1 1 4 1 4 3 3 3 2 2	5

Каталог: forum -> attachment
forum -> Kiểm tra kiến thức Sinh học lớp 12
forum -> Danh sách giao lưu đại học Sookmyung ( 8/1/2014) Lớp 4H12
attachment -> CHƯƠng I: LẮp ráp và CÀI ĐẶt máy tíNH
attachment -> BÀi tập lớn môn: Kiến trúc máy tính Yêu cầu: Tìm hiểu kiến trúc mips
attachment -> BÀI 1 : html cơ sở 1-Thành phần-Element

tải về 418.79 Kb.

Chia sẻ với bạn bè của bạn: