CÁC BÀI TOÁN VỀ ĐỒ THỊ THEO CHUYÊN ĐỀ

A. Chuyên đề Tìm kiếm theo chiều rộng (BFS)

  1. Lucky Numbers

Mã bài: LUCKYNUM     

2. VOI06 Quân tượng

Mã bài: QBBISHOP

3. Gặm cỏ

Mã bài: VMUNCH

4. Bãi cỏ ngon nhất

Mã bài: VBGRASS

5. Tương đương hóa hai từ

Mã bài: VWORDS

6. GUMBI

Mã bài: LEM2

B. Chuyên đề Tìm kiếm theo chiều sâu DFS

1.Quảng cáo

Mã bài: ADS

2. Truyền tin

Mã bài: MESSAGE

3. Bộ ba cao thủ

Mã bài: NKTRIO

4. Mạng máy tính an toàn

Mã bài: SAFENET2

5. Vòng đua xe đạp

Mã bài: BIC

6. Xây cầu

Mã bài: BRIDGES

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

1.Bin Laden

Mã bài: BINLADEN

2. Xúc xắc

Mã bài: XUCXAC

3. Traffic Network

Mã bài: TRAFFICN

4. Roads

Mã bài: ROADS

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

Mã bài: BESTSPOT

6. Số phụ thuộc

Mã bài: SUMS

7. CENTRE

Mã bài: CENTRE28

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

Mã bài: FLOYD 

9. Hai đường đi

Mã bài: HIWAY

Vận chuyển hàng

Mã bài: QBTRANS

10. VOI06 Kênh xung yếu

Mã bài: QBCIRARC

11. Mạng 3 đỉnh

Mã bài: THREE

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

Mã bài: QBBUILD

D. Chuyên đề: CHU TRÌNH EULER

  1. Người đưa thư

Mã bài: NKPOS

E. Chuyên đề: CÂY KHUNG NHỎ NHẤT

  1. Cây khung nhỏ nhất ( HEAP )

Mã bài: QBMST

2. Vòng đua F1

Mã bài: NKRACING

3. Tưới nước đồng cỏ

Mã bài: FWATER

4. Xây dựng thành phố

Mã bài: NKCITY

F. Chuyên đề: CẶP GHÉP

1.Cặp ghép không trọng số

Mã bài: MATCH1

2. Bộ ghép đầy đủ trọng số cực tiểu

Mã bài: MATCH2

3. Cặp ghép cực đại trên đồ thị hai phía

Mã bài: NKBM

4. Phân công hoàn thành sớm nhất

Mã bài: ASSIGN1

5. Boxes

Mã bài: BOXES

6. IOI2008

Mã bài: IOI2008

7. Harry Potter và mê cung tử thần

Mã bài: NHP

8. Fast Maximum Matching

Mã bài: FMATCH

G. Chuyên đề: LUỒNG TRÊN MẠNG

1.Luồng cực đại trên mạng

Mã bài: NKFLOW

2. Báo động đỏ

Mã bài: ALERT

3. Monkey island

Mã bài: NKTRAFIC

4. Hệ thống đèn

Mã bài: LIGHT

5. Luồng với chi phí nhỏ nhất

Mã bài: MINCOST

6. Phòng máy

Mã bài: WIFI

7. Trao đổi thông tin

Mã bài: KWAY

H. Các bài toán đồ thị trong các kỳ thi Quốc gia

1.Mạng máy tính (2006 – vòng 1)

2. Quân tượng (2006 – vòng 1)

3. Kênh xung yếu (2006 – vòng 1)

4. Robot cứu hỏa (2007 - vòng 1)

5. Lò cò (2008 – vòng 1)

6. Nút st - xung yếu (2009 – vòng 1)

7. Ổn định (2010 – vòng 1)

8. Nâng cấp mạng (2011 – vòng 1)

9. Phân cụm (2006 – vòng 2)

Phân cụm là một bài toán có ý nghĩa ứng dụng quan trọng trong các lĩnh vực như học máy, khai phá dữ liệu, thu thập dữ liệu và đòi hỏi phân hoạch tập các điểm dữ liệu ra thành các nhóm sao cho các điểm trong cùng một nhóm là “gần nhau”  và “cách xa” các nhóm khác. Trong bài này chúng ta xét một dạng đơn giản của bài toán phân cụm. 

Cho tập gồm n đối tượng X = {x1, x2, ..., xn}, khoảng cách d(xi, xj) giữa mọi cặp xixj và một số nguyên dương k (k n). Giả thiết là d(xi, xj) là các số nguyên dương, d(xi, xj) = d(xj, xi) và d(xi, xi) = 0, với mọi i, j = 1, 2, ..., n. Ta gọi một cách phân cụm là một  cách phân hoạch tập X ra thành k tập con khác rỗng (mỗi tập con như vậy được gọi là một cụm). Cho C = {C1, C2, ..., Ck}  là một cách phân cụm, ta gọi độ phân tách của cách phân cụm C (ký hiệu là (C )) là giá trị nhỏ nhất trong số các khoảng cách giữa hai phần tử bất kỳ thuộc hai cụm khác nhau, nghĩa là

(C ) = min {d(u,v): uCp, vCq , pq }.

Yêu cầu: Tìm cách phân cụm với độ phân tách là lớn nhất.

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

  • Dòng đầu tiên chứa hai số nguyên n và k.
  • Dòng thứ i trong số n dòng tiếp theo ghi các số d(xi, x1), d(xi, x2), ..., d(xi, xn), i = 1, 2, ..., n.

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

Kết quả: Ghi ra file văn bản CLUSTER.OUT độ phân tách của cách phân cụm tìm được.

Ví dụ:

CLUSTER.INPCLUSTER.OUT
4 3
0 1 2 3
1 0 2 3
2 2 0 3
3 3 3 0
2

Hạn chế: 

  • Trong tất cả các test: 1  n  200; d(xi, xj)  32000, i, j = 1, 2, ..., n. 
  • Có 50% số lượng test với n  100.

10. Thoát mê cung (2006 – vòng 2)

Mê cung có dạng lưới ô vuông hình chữ nhật kích thước mxn, các dòng của lưới được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Mỗi ô là một phòng. Vách ngăn giữa hai phòng hoặc giữa phòng với phần bên ngoài có thể có hoặc không có cửa thông nhau. Mê cung được mô tả bởi bản đồ số B là bảng mxn số nguyên, trong đó thành phần ở vị trí giao của dòng i với cột j là Bij (0 ≤ Bij ≤ 4) cho biết số vách ngăn có cửa của ô (i,j). Thời gian đi từ một ô sang ô bên cạnh hoặc ra ngoài là 1, nếu vách ngăn tương ứng có cửa. 

http://www.spoj.pl/content/paulmcvn:escape.jpg

Yêu cầu: Cho biết m, n, bản đồ số B và (u, v) – toạ độ một ô nào đó trong mê cung. Hãy xác định một cách đặt cửa cho các phòng đảm bảo thỏa mãn bản đồ B và thời gian T để thoát ra khỏi mê cung từ phòng (u, v) là ít nhất. Biết rằng dữ liệu bản đồ số B đảm bảo có ít nhất một cách đặt cửa để thoát ra ngoài. 

Dữ liệu vào

  • Dòng đầu tiên chứa 4 số nguyên m, n, u và v. 
  • Dòng thứ i trong m dòng sau chứa n số nguyên Bi1, Bi2,. . ., Bin. 

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

Kết qủa

Đưa ra số nguyên T. 

Hạn chế

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

Ví dụ

Dữ liệu mẫu

4 4 3 3

1 1 1 0

1 0 3 2

1 1 1 0

0 1 0 0

Kết qủa

3

11. Phương án phòng thủ (2007 – vòng 2)

Để phòng vệ cho một trận địa có dạng lưới ô vuông m × n, Bộ chỉ huy quân sự đã tính toán về việc thiết lập các chốt phòng thủ theo khu vực, mỗi chốt sẽ được đặt tại một trong các ô vuông trên trận địa và mỗi ô vuông có không quá một chốt. 

Giả sử các hàng ngang được đánh số từ 1 đến m theo trình tự từ trên xuống dưới và hàng dọc được đánh số từ 1 đến n theo trình tự từ trái sang phải. Ô nằm trên giao của hàng ngang i và hàng dọc j được gọi là ô (i,j).

Hệ thống phòng thủ cần phải bảo đảm mỗi hàng ngang, hàng dọc đều có đủ số lượng chốt cần thiết. Bên cạnh đó, dựa vào thông tin tình báo, các chuyên gia cũng tính toán được khả năng đánh phá của địch pij (pij<1000) vào từng ô (i,j) trên trận địa (pij càng lớn nghĩa là khả năng địch đánh phá ô (i,j) càng cao). Căn cứ vào đó, người chỉ huy sẽ bố trí các chốt phòng thủ. 

Bạn được mời làm cố vấn quân sự, hãy xác định phương án đặt vị trí các chốt phòng thủ trên trận địa đảm bảo được các yêu cầu về số lượng chốt phòng thủ đồng thời sao cho tổng khả năng đánh phá của địch vào các vị trí được chọn là nhỏ nhất. 

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

·         Dòng đầu tiên chứa 2 số nguyên dương m, n (m, n ≤ 100), 

·         Dòng thứ 2 chứa m số nguyên không âm lần lượt là số lượng chốt cần có từ hàng ngang thứ 1 đến hàng ngang thứ m, 

·         Dòng thứ 3 chứa n số nguyên không âm lần lượt là số lượng chốt cần có từ hàng dọc thứ 1 đến hàng dọc thứ n, 

·         m dòng tiếp theo, mỗi dòng chứa n số nguyên không âm mô tả các giá trị pij. 

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

Kết quả: ghi ra file văn bản DEFEND.OUT duy nhất số -1 trong trường hợp không có phương án lập hệ thống chốt phòng thủ. Ngược lại, ghi ra số nguyên là tổng khả năng đánh phá của địch vào các vị trí được chọn tương ứng với phương án tìm được. 

Ví dụ: 

DEFEND.INPDEFEND.OUT
4 4
2 2 2 2
2 2 2 2
1 1 8 8
9 1 10 2
5 5 2 3
2 4 10 10
22