trang chủ / đề bài / prevoi25_war

Chiến tranh

Đề bài

Mô tả

Bách thách đố Dương và Thanh chơi một trò chơi. Có một đất nước gồm n thành phố, các thành phố được đánh số từ 0 đến n−1. Các thành phố được nối với nhau bằng m con đường 2 chiều. Những con đường này sẽ nối giữa 2 thành phố khác nhau và giữa 2 thành phố có thể có nhiều con đường khác nhau.

Hiện tại đất nước đang diễn ra cuộc chiến giữa đội quân A và đội quân B. Mỗi đội quân có thể di chuyển dọc theo các con đường để đi từ thành phố này sang thành phố khác. Đất nước muốn ngăn chặn chiến tranh diễn ra bằng cách phá hủy một vài con đường sao cho hai đội quân này không thể gặp được nhau và người chơi muốn giảm thiểu tối đa kinh phí để làm việc đó. Hai đội quân có thể gặp nhau khi tồn tại một đường đi gồm các con đường chưa bị phá hủy giữa 2 thành phố mà 2 đội quân này đang chiếm đóng (các con đường trên đường đi có thể qua những thành phố khác).

Người chơi sẽ phải chọn 2 thành phố khác nhau cho 2 đội quân này chiếm đóng và số điểm của người chơi là kinh phí ít nhất để đất nước ngăn chặn chiến tranh. Cả 2 bạn đều muốn số điểm của mình càng thấp càng tốt. Dương là một con người rất thông minh nên cậu dễ dàng tìm được cách chọn 2 thành phố tối ưu nhất. Tuy nhiên Thanh không hiểu về game nên đã chọn ngẫu nhiên 2 thành phố bất kì trong n thành phố để làm đáp án: thành phố của đội A và thành phố của đội B là một cặp có thứ tự gồm hai thành phố khác nhau, mỗi cặp trong n·(n−1) cặp được chọn với xác suất như nhau.

Sau cùng, Bách muốn biết số điểm của Dương và trung bình số điểm của Thanh sẽ là bao nhiêu?

Dữ liệu vào

  • Dòng đầu tiên ghi 3 số T,n,m (1≤T≤2).
  • Mỗi dòng trong m dòng tiếp theo ghi 3 số ui,vi,wi (0≤ui,vi<n,ui≠vi,1≤wi≤106) chỉ một con đường nối 2 thành phố ui và vi và cần wi đồng tiền để phá hủy con đường đó.

Dữ liệu ra

  • Nếu T=1 in ra số điểm của Dương.
  • Nếu T=2 in ra số điểm trung bình của Thanh nhân với n·(n−1). Đảm bảo đáp án cần in ra luôn là số nguyên.

Ràng buộc

  • 1≤T≤2, 2≤n≤2000, 1≤m≤4000.
  • 0≤ui,vi<n, ui≠vi, 1≤wi≤106.
  • Nếu T=2 thì n≤400 và m≤1000.

Subtasks

  • Subtask 1 (20% số điểm): n≤18, m≤100.
  • Subtask 2 (40% số điểm): n≤50, m≤100.
  • Subtask 3 (20% số điểm): T=1, n≤2000, m≤4000.
  • Subtask 4 (20% số điểm): T=2, n≤400, m≤1000.

Ví dụ

Input Output Giải thích
1 6 9
0 1 1
0 2 7
1 2 1
1 3 3
1 4 2
2 4 4
3 4 1
3 5 6
4 5 2
6 Kinh phí ít nhất để tách từng cặp thành phố (u,v) với u<v: (0,1)=6, (0,2)=8, (0,3)=6, (0,4)=6, (0,5)=6, (1,2)=6, (1,3)=6, (1,4)=7, (1,5)=6, (2,3)=6, (2,4)=6, (2,5)=6, (3,4)=6, (3,5)=8, (4,5)=6. Chẳng hạn cặp (0,3) không có con đường nối trực tiếp nhưng vẫn cần 6 đồng: phá các con đường 0−1, 1−2, 2−4 (tách {0,2} khỏi phần còn lại). Dương chọn cặp có kinh phí nhỏ nhất là 6.
2 6 9
0 1 1
0 2 7
1 2 1
1 3 3
1 4 2
2 4 4
3 4 1
3 5 6
4 5 2
190 Cùng đồ thị. Tổng kinh phí 15 cặp ở trên là 95; mỗi cặp xuất hiện hai lần trong n·(n−1)=30 cặp có thứ tự, nên đáp án là 2·95=190.

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