CÁC BÀI TOÁN VỀ ĐỒ THỊ THEO CHUYÊN ĐỀ
A. Chuyên đề Tìm kiếm theo chiều rộng (BFS)
- 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
- Người đưa thư
Mã bài: NKPOS
E. Chuyên đề: CÂY KHUNG NHỎ NHẤT
- 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)
3. Kênh xung yếu (2006 – vòng 1)
4. Robot cứu hỏa (2007 - vòng 1)
6. Nút st - xung yếu (2009 – 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 xi xj 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): u Cp, v Cq , p q }.
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.INP | CLUSTER.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.

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.INP | DEFEND.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 |



Bình luận