Thuật toán LCA

Tải về thuật toán LCA

Thuật toán KARP

Tải về Thuật toán Karp

TRUY BẮT TRÙM KHỦNG BỐ

Trùm khủng bố B.L. trốn tránh sự truy đuổi của cảnh sát ở một hệ thống cống thoát nước ngầm của thành phố. Hai đoạn đường ống bất kỳ trong hệ thống cống có nhiều nhất một nút chung là đầu mút chung cho cả hai. Tên khủng bố ẩn nấp tại một trong những nút như vậy. Để ngăn cản sự truy bắt của cảnh sát tên khủng bố đã đặt bom hẹn giờ tại một số nút. Việc đi qua nút như vậy là không thể  thực hiện được sau khi bom phát nổ. Cảnh sát Bondy muốn bắt tên khủng bố này. Trong tay Bondy có sơ đồ của hệ thống cống ngầm, trong đó chỉ rõ vị trí nút mà tên khủng bố ẩn nấp và vị trí các nút có đặt bom và thời điểm hẹn phát nổ của chúng. Tại thời điểm 0 Bondy bắt đầu cuộc truy đuổi từ một nút xuất phát và muốn đến được nút ẩn nấp của tên khủng bố sau thời gian nhanh nhất. Bondy sẽ hy sinh nếu bom nổ đúng lúc anh ta đi qua nút chứa nó, trái lại anh ta sẽ không bị tổn thương và có thể tiếp tục truy đuổi.

Yêu cầu: Xác định thời gian nhỏ nhất cần thiết để Bondy có thể bắt được tên khủng bố, nếu như điều đó có thể thực hiện được.

Dữ liệu: Vào từ file văn bản CAPTION.INP:

+ Dòng đầu tiên chứa các số nguyên dương N, M, S, T. N là số lượng nút, các nút được đánh số từ 1 đến N. M là số lượng đoạn đường ống. Giữa hai nút bất kỳ có nhiều nhất là một đoạn đường ống. S là chỉ số của nút xuất phát của Bondy, và T là nút mà tên khủng bố ẩn nấp. (1 £ S, T £ N £ 100, 1 £ M £ N²).

+ Dòng thứ i trong số N dòng tiếp theo chưa số 0 nếu nút này không có bom và chứa số nguyên dương X_i cho biết thời điểm phát nổ của quả bom ở nút i (i = 1, 2, ..., N).

+ Mỗi dòng trong số M dòng tiếp theo chứa chỉ số của hai đầu mút của một đoạn đương ống và số nguyên dương Y là thời gian cần thiết để đi từ đầu này đến đầu kia của đoạn đường ống này. (Y £ 1000).

Kết quả: Ghi ra file văn bản CAPTION.OUT thời gian nhỏ nhất mà Bondy cần có để bắt giữ tên khủng bố nếu như việc đó có thể thực hiện được (như vậy, sẽ ghi 0 nếu Bondy xuất phát tại nút mà tên khủng bố ẩn nấp). Trái lại cần ghi -1.

Ví dụ:

CAPTION.INP	CAPTION.OUT		CAPTION.INP	CAPTION.OUT
4 4 1 4 0 0 5 0 2 1 3 3 4 4 3 2 2 1 3 4	8		3 2 1 3 0 1 0 1 2 3 2 3 1	-1

SOLUTION TEST

HÀNH TRÌNH DU LỊCH

Nguồn: PreVOI2014-2015
Sau khi xây dựng xong khu du lịch, thầy Minh bắt tay vào khai tác bằng cách tổ chức các hành trình du lịch. Khu du lịch gồm n địa điểm đánh số từ 1 đến n. Hệ thông giao thông trong vùng gồm m tuyến đường một chiều khác nhau, tuyến đường thứ j (j=1,2,…,m) cho phép đi từ địa điểm u_j đến địa điểm v_j với chi phí đi lại là số nguyên dương c_j. Công ty vừa nhận được hợp đồng yêu cầu xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch bất kỳ và đi thăm một số địa điểm du lịch sau đó quay về điểm xuất phát mà chi phí trung bình là nhỏ nhất. Chi phí trung bình được tính bằng tổng chi phí của các tuyến đường mà hành trình đi qua chia cho số tuyến đường trên hành trình.

Yêu cầu: Cho thông tin về hệ thống giao thông, hãy xây dựng một hành trình du lịch với chi phí trung bình nhỏ nhất.

Dữ liệu vào: Từ tệp văn bản TOUR.INP

+ Dòng đầu tiên chứa hai số nguyên dương n<=10³ và m<=10⁴

+ Dòng thứ j trong số m dòng tiếp theo chứa 3 số nguyên u_j, v_j, c_j cho biết thông tin về tuyến đường thứ j. Giải thiết u_j≠v_j; c_j<=10⁹ với j=1,2,…,m.

Kết quả: ghi ra tệp văn bản TOUR.OUT giá trị tổng chi phí chia cho số địa điểm trên hành trình tìm được làm tròn đến 2 chữ số sau dấu chấm thập phân. Ghi ra xâu NO TOUR nếu không tìm được hành trình du lịch thỏa mãn yêu cầu.

Ví dụ:

TOUR.INP	TOUR.OUT
6 8 1 2 4 2 4 1 4 3 3 3 1 4 4 1 1 3 5 5 5 3 1 5 6 7	2.00
2 1 1 2 3	NO TOUR

Giới hạn:

25% số điểm có N<=10

25% số điểm có N<=20

25% số điểm có N<=100

25% số điểm có N<=1000

Thuật toán KARP TEST CODE

+++++++++++++++++++++
+    TRẦN THIỆN DINH    +
+    Chuyên Tin 2013-2016  +
+ Lê Quý Đôn - Khánh Hòa +
+++++++++++++++++++++

Hội thảo bằng điện thoại

Một công ty điện thoại cần tổ chức một cuộc hội thảo cho 3 khách hàng trên đường trường thông. Dịch vụ cần đảm bảo cho 3 khách hàng có thể trao đổi với nhau đồng thời. Mỗi khách hàng có thể thâm nhập vào mạng truyền thông qua các cổng thâm nhập. mạng truyền thông bao gồm các cổng thâm nhập được nối với nhau bằng các kênh  điện thoại hai chiều. Ba khách hàng cần thâm nhập vào mạng từ 3 cổng khác nhau sao cho tổng chi phí để liên kết họ là ít nhất. Chú ý là được phép liên kết hai cổng thâm nhập bất kỳ. Bạn được biết các kênh nối giữa các cổng cùng với chi phí liên kết chúng. Bạn cần tìm liên kết đòi hỏi chi phí ít nhất để nối 3 cổng thâm nhập của 3 khách hàng tham gia hội thảo. Các cổng được đánh số từ 1 đến N.

Dữ liệu vào: từ file văn bản CONF.INP

+ Dòng đầu tiên chứa hai số nguyên N và E, trong đó N≤100 là số cổng, E là số kênh giữa các cổng

+ Mỗi dòng thứ K trong số E dòng tiếp theo chứa 3 số nguyên i, j, c_ij cho biết kênh nối thứ k nối hai cổng i với j và chi phí để liên kết hai cổng này là c_ịj (1≤c_ij≤100)

+ Dòng cuối cùng chứa 3 số nguyên là chỉ số của 3 cổng mà từ đó 3 khách hàng tham gia hội thảo thâm nhập vào mạng

Dữ liệu ra: ghi vào file CONF.OUT

+ Dòng đầu tiên chứa S là tổng chi phí theo cách liên kết tìm được và R là số kênh nối cần sử dụng

+ Một trong các dòng tiếp theo chứa 2 số của hai đầu mút của kênh cần sử dụng trong cách liên kết đó.

CONF.INP	CONF.OUT
8 12 1 2 20 2 3 8 2 4 3 2 5 3 2 6 6 3 5 2 3 6 9 4 7 5 5 6 1 5 7 7 6 8 4 7 8 6 1 4 6	27 4 1 2 2 4 2 5 5 6

 

SOLUTION - TEST