150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 9

137. PHCho một đồ thị vô hướng G = (V, E) có n đỉnh và m cạnh, không có đỉnh cô lậpHãy chọn ra một tập ít nhất các cạnh để tất cả các đỉnh của đồ thị đều là đầu mút của ít nhất một cạnh trong tập đã chọn ! Dữ liệu: Vào từ file văn bản COVER.INP
Nội dung trích xuất từ tài liệu:
150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 9 137. PHCho một đồ thị vô hướng G = (V, E) có n đỉnh và m cạnh, không có đỉnh cô lậpHãy chọn ra một tập ít nhất các cạnh để tất cả các đỉnh của đồ thị đều là đầu mút của ít nhấtmột cạnh trong tập đã chọn !Dữ liệu: Vào từ file văn bản COVER.INP• Dòng 1: Chứa hai số n, m là số đỉnh và số cạnh của đồ thị (1 ≤ n ≤ 100)• m dòng tiếp theo, mỗi dòng ghi hai số u, v tương ứng với một cạnh (u, v) của đồ thịKết quả: Ghi ra file văn bản COVER.OUT• Dòng 1: Ghi số k là số cạnh được chọn• k dòng tiếp theo, mỗi dòng ghi chỉ số hai đỉnh đầu mút của một cạnh được chọnChú thích nho nhỏ : Bài này sử dụng kiến thức không phổ biến ! Bởi vậy không có gì là khóhiểu nếu như bạn không làm được !Ví dụ: COVER.INP COVER.OUT 10 11 5 12 61 61 28 24 34 28 5 10 34 97 36 56 59 5 10 78 97 147 138. DI CHUY N RÔ-B TCho một đồ thị có hướng G gồm n đỉnh và m cung, hai con Rô-bốt đứng tại hai đỉnh nào đó.Yêu cầu:Chuyển nhanh nhất hai con Rô-bốt đến gặp nhau tại một đỉnh của đồ thị, biết rằng cả hai conRô-bốt chỉ được chạy theo các cung định hướng và không được dừng lại cho tới lúc gặp nhau tạimột đỉnh nào đó. Thời gian Rô-bốt đi qua một cung bất kỳ luôn là 1 đơn vị thời gianDữ liệu: Vào từ file văn bản RMOVE.INP• Dòng 1: chứa 4 số nguyên dương n, m, A, B. Ở đây A và B lần lượt là vị trí của con rô-bốt thứ nhất và vị trí của con rô-bốt thứ hai, 2 ≤ n ≤ 250, 1 ≤ m ≤ 60000.• m dòng tiếp theo, mỗi dòng chứa hai số u, v tương ứng với một cung (u, v) của đồ thịKết quả: Ghi ra file văn bản RMOVE.OUT• Dòng 1: Ghi thời gian tính từ lúc bắt đầu di chuyển cho tới lúc hai rô-bốt gặp nhau• Dòng 2: Ghi hành trình của con rô-bốt thứ nhất, theo đúng thứ tự từ đỉnh A tới đỉnh gặp nhau• Dòng 3: Ghi hành trình của con rô-bốt thứ hai, theo đúng thứ tự từ đỉnh B tới đỉnh gặp nhauCác số trên một dòng của Input/Output file cách nhau ít nhất một dấu cáchRàng buộc: Luôn có phương án thực hiện yêu cầu trênGiới hạn : Chương trình chạy trên Turbo Pascal.Ví dụ: RMOVE.INP RMOVE.OUT 4512 3 3 12 1212 4 21 2432 24 32 1 2 43 148 139. TR M NGHMột toán kỵ sĩ bỏ ngựa đi thám hiểm một khu rừng và đến khi trời tối, họ muốn đi về những trạmnghỉ. Rất may là các kỵ sĩ đều có bản đồ khu rừng trong tay, nhờ đó có thể xác định chính xác vị trícủa họ, các trạm nghỉ, các khu vực có thú dữ và tất nhiên cả vị trí của các con ngựa (nơi họ đã bỏlại).Mỗi kỵ sĩ sẽ phải chọn cho mình một con ngựa, một trạm nghỉ và dùng còi siêu âm gọi con ngựa đóvề trạm nghỉ đã chọn. Mỗi trạm nghỉ chỉ đủ chỗ cho một kỵ sĩ và một con ngựa.Giả sử rằng có m trạm nghỉ, n kỵ sĩ, n con ngựa và bạn là một trong số những kỵ sĩ đó. Hãy vạchra hành trình cho các kỵ sĩ và các con ngựa để thời gian tính từ lúc bắt đầu cho tới khi tất cả cáccon ngựa và các kỵ sĩ về tới trạm nghỉ tương ứng là nhỏ nhất.Bản đồ khu rừng được mã hoá bằng một lưới ô vuông đơn vị kích thước pxq. Trên mỗi ô ghi mộttrong 5 ký hiệu:• %: Địa điểm có thú dữ• .: Địa điểm an toàn (không có thú dữ)• &: Địa điểm an toàn có một con ngựa đang đứng• *: Địa điểm an toàn có một kỵ sĩ đang đứng• @: Trạm nghỉVới 1 đơn vị thời gian, mỗi kỵ sĩ và mỗi con ngựa có thể thực hiện một bước đi. Nhìn trên bản đồ,mỗi bước đi của một kỵ sĩ là một phép di chuyển từ ô đang đứng sang một trong các ô kề cạnh,bước đi này được mã hoá bằng một trong 4 ký hiệu {E, W, S, N}. Mỗi bước đi của một con ngựa làmột phép di chuyển như một nước đi của quân mã theo luật cờ, bước đi này được mã hoá bằng mộttrong 8 ký hiệu {1, 2, 3, 4, 5, 6, 7, 8}. Các kỵ sĩ cũng như các con ngựa không được đi tới ô có thúdữ hay đi ra ngoài bản đồ. Các ký hiệu tương ứng với các hướng đi được chỉ ra trong hình dưới đây: 6 7 N 5 ...