trang chủ / đề bài / icpcwf16_b

Phân công chi nhánh

Đề bài

Mô tả

Công ty Sản phẩm Tiêu dùng Sáng tạo (ICPC) đang lên kế hoạch khởi động một dự án tuyệt mật. Dự án gồm s dự án con. Có b≥s chi nhánh của ICPC tham gia dự án và ICPC muốn giao mỗi chi nhánh cho một trong các dự án con. Nói cách khác, các chi nhánh sẽ được chia thành s nhóm rời nhau, mỗi nhóm phụ trách một dự án con.

Vào cuối mỗi tháng, mỗi chi nhánh sẽ gửi một thông điệp tới mọi chi nhánh khác trong cùng nhóm của nó (mỗi chi nhánh nhận một thông điệp khác nhau). ICPC có một giao thức liên lạc riêng. Mỗi chi nhánh i có một khóa bí mật ki mà chỉ chi nhánh đó và trụ sở chính của ICPC biết. Giả sử chi nhánh i muốn gửi một thông điệp tới chi nhánh j. Chi nhánh i mã hóa thông điệp bằng khóa ki của mình. Một người đưa thư tin cậy nhận thông điệp này tại chi nhánh i và mang nó tới trụ sở chính của ICPC. Trụ sở giải mã thông điệp bằng khóa ki rồi mã hóa lại bằng khóa kj. Sau đó người đưa thư mang thông điệp mới được mã hóa tới chi nhánh j, nơi nó được giải mã bằng khóa kj của chi nhánh đó. Vì lý do an ninh, mỗi người đưa thư chỉ được mang một thông điệp mỗi lần.

Cho một mạng lưới đường đi cùng vị trí của các chi nhánh và trụ sở chính trong mạng lưới này, hãy xác định tổng quãng đường nhỏ nhất mà những người đưa thư cần đi để chuyển hết các thông điệp cuối tháng, xét trên mọi cách phân chia các chi nhánh vào các dự án con.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên n, b, s và r, trong đó n là số giao lộ, b là số chi nhánh, s là số dự án con và r là số con đường. Các giao lộ được đánh số từ 1 tới n. Các chi nhánh nằm ở các giao lộ 1 tới b, còn trụ sở chính nằm ở giao lộ b+1.

Mỗi dòng trong r dòng tiếp theo chứa ba số nguyên u, v và ℓ, cho biết có một con đường một chiều từ giao lộ u tới một giao lộ khác v với độ dài ℓ.

Dữ liệu ra

In ra tổng quãng đường nhỏ nhất mà những người đưa thư cần đi.

Ràng buộc

  • 2≤n≤5000, 1≤b≤n−1, 1≤s≤b, 1≤r≤50000.
  • 1≤u,v≤n, u≠v, 0≤ℓ≤10000.
  • Không có cặp có thứ tự (u,v) nào xuất hiện quá một lần.
  • Từ mọi giao lộ đều có thể đi tới mọi giao lộ khác.

Ví dụ

Input Output Giải thích
5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2
13 Trụ sở ở giao lộ 5. Tổng quãng đường đi từ chi nhánh tới trụ sở và từ trụ sở về chi nhánh lần lượt là 1+2=3, 1+1=2, 2+2=4, 0+4=4 với các chi nhánh 1,2,3,4. Chia thành nhóm {1,2} và {3,4}: mỗi chi nhánh gửi một thông điệp và nhận một thông điệp, tổng là (3+2)+(4+4)=13.
5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 10
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2
24 Các tổng quãng đường khứ hồi lần lượt là 3,2,7,14. Chia thành nhóm {1,2,3} và {4}: mỗi chi nhánh trong nhóm đầu gửi 2 thông điệp và nhận 2 thông điệp, tổng là 2·(3+2+7)=24; chi nhánh 4 đứng một mình không gửi gì.

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