trang chủ / đề bài / icpcwf10_d

Các lâu đài

Đề bài

Mô tả

Chiến tranh đóng vai trò quan trọng trong lịch sử thế giới. Khác với chiến tranh hiện đại, các đạo quân thời trung cổ chủ yếu tìm cách chiếm và giữ các lâu đài, nơi ở kiên cố của các lãnh chúa và quý tộc. Quy mô của đạo quân tấn công là yếu tố quan trọng quyết định khả năng chiếm và giữ một trong những kiệt tác kiến trúc này.

Cần có một số lính tối thiểu để chiếm được một lâu đài. Một số lính sẽ tử trận trong cuộc tấn công. Sau khi chiếm lâu đài, một số lính phải ở lại để phòng thủ trước sự tấn công của kẻ thù khác. Dĩ nhiên các con số này khác nhau ở từng lâu đài. Người chỉ huy phải tính toán số lính cần thiết để giành chiến thắng. Ví dụ, khu vực trong hình dưới đây có năm lâu đài, mỗi lâu đài ghi bộ ba (a,m,g) được giải thích ở phần dữ liệu vào. Lâu đài ở góc dưới bên phải cần ít nhất 20 lính để tấn công thắng lợi; không lính nào tử trận trong cuộc tấn công, và phải để lại 10 lính trong lâu đài khi đạo quân đi tiếp.

tree
1 2
1 3
1 4
3 5
name 1 10,5,10
name 2 20,10,5
name 3 10,10,5
name 4 5,5,5
name 5 20,0,10

Trong bài này bạn phải tìm quy mô nhỏ nhất của đạo quân cần thiết để chiếm và giữ toàn bộ các lâu đài trong một khu vực. Vì lý do an ninh, giữa hai lâu đài bất kỳ trong khu vực có đúng một con đường (hai chiều). Việc tiến vào vùng lân cận của một lâu đài chưa bị chiếm sẽ bắt đầu một cuộc tấn công vào lâu đài đó. Lâu đài nào cũng có thể là lâu đài bị tấn công đầu tiên, không cần quan tâm đạo quân đã đến đó bằng cách nào. Mỗi khi chiếm được một lâu đài, số lính cần thiết được để lại trong lâu đài để phòng thủ, và phần còn lại của đạo quân đi tiếp để chiến đấu ở một lâu đài khác, nếu vẫn còn lâu đài chưa bị chiếm. Đạo quân có thể đi qua vùng lân cận của một lâu đài đã chiếm một cách an toàn. Nhưng vì nguy cơ bị tấn công, đạo quân chỉ được đi trên con đường giữa hai lâu đài nhiều nhất hai lần (tức là nhiều nhất một lần theo mỗi chiều).

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, mỗi bộ ứng với một khu vực. Mô tả các lâu đài của mỗi khu vực chiếm nhiều dòng:

  • Dòng đầu tiên chứa số nguyên n (n≤100): số lâu đài trong khu vực.
  • Mỗi dòng trong n dòng tiếp theo chứa ba số nguyên a, m và g (1≤a≤1000, 0≤m≤a, 1≤g≤1000): số lính tối thiểu cần có để tấn công và chiếm thành công lâu đài, số lính dự kiến tử trận trong cuộc tấn công, và số lính phải để lại lâu đài để phòng thủ. Các lâu đài được đánh số từ 1 đến n, các dòng mô tả được cho theo thứ tự số hiệu tăng dần.
  • Mỗi dòng trong n−1 dòng còn lại chứa hai số nguyên là số hiệu của hai lâu đài được nối trực tiếp bởi một con đường.

Sau mô tả của khu vực cuối cùng là một dòng chứa số 0.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test và số lính ít nhất mà đạo quân cần có để chinh phục mọi lâu đài trong khu vực, theo định dạng trong ví dụ.

Ràng buộc

  • 1≤n≤100.
  • 1≤a≤1000, 0≤m≤a, 1≤g≤1000.
  • Các con đường nối mọi lâu đài, giữa hai lâu đài bất kỳ có đúng một đường đi.

Ví dụ

Input Output Giải thích
3
5 5 5
10 5 5
5 1 1
1 3
2 3
5
10 5 10
20 10 5
10 10 5
5 5 5
20 0 10
1 2
1 3
1 4
3 5
0
Case 1: 22
Case 2: 65
Bộ 1: bắt đầu với 22 lính ở lâu đài 1 (cần 10, mất 5+5, còn 12), sang lâu đài 3 (cần 5, mất 1+1, còn 10), rồi sang lâu đài 2 (cần 10, mất 5+5). Bộ 2 là khu vực trong hình: bắt đầu ở lâu đài 1, đánh nhánh gồm lâu đài 3 và 5, quay về 1, đánh lâu đài 2, quay về 1, rồi đánh lâu đài 4; tổng số lính tử trận và ở lại là 65 nên không thể dùng ít hơn.
1
7 3 5
4
3 1 1
8 2 4
6 6 1
2 0 2
1 2
1 3
1 4
0
Case 1: 8
Case 2: 17
Bộ 1: chỉ cần 7 lính để tấn công nhưng 3 lính tử trận và phải để lại 5 lính, nên cần 8. Bộ 2: tổng số lính tử trận và ở lại là 2+6+7+2=17; bắt đầu ở lâu đài 1 rồi đánh lần lượt các lâu đài 2, 3, 4 thì đủ quân ở mọi lúc.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0