trang chủ / đề bài / icpc21_mt_a

Hệ thống đám mây DUT

Đề bài

Mô tả

Tuần trước, chúng ta đã giúp trường HCMUS tính tốc độ truyền dữ liệu giữa N máy chủ của họ. Hệ thống đó hoạt động rất tốt và trở thành hình mẫu cho các trường đại học khác. Trường Đại học Bách khoa Đà Nẵng (DUT) muốn xây dựng một hệ thống tương tự.

DUT đã có sẵn N máy chủ, họ muốn kết nối chúng bằng các dây cáp hai chiều. Mỗi cặp máy chủ được nối bởi nhiều nhất 1 dây cáp (có thể không có dây nào).

Dây cáp nối máy chủ u và máy chủ v có khả năng truyền tải Cu,v megabit mỗi nano giây. Gọi Fu,v là tốc độ truyền dữ liệu giữa máy chủ u và máy chủ v. Để truyền dữ liệu từ máy chủ u đến máy chủ v, dữ liệu có thể được chia thành nhiều phần và truyền theo nhiều đường khác nhau; tổng lượng dữ liệu đi qua mỗi dây cáp không vượt quá khả năng truyền tải của dây đó. Nói cách khác, Fu,v là luồng cực đại giữa u và v trong mạng dây cáp.

Ví dụ, xét mạng 4 máy chủ với các dây cáp 1−2 (50), 1−3 (20), 1−4 (30), 2−4 (10), 3−4 (70). Để truyền dữ liệu từ máy chủ 1 đến máy chủ 4, dữ liệu có thể chia thành 3 phần và truyền theo 3 đường:

  • 1−4 (30 Mb mỗi nano giây);
  • 1−3−4 (20 Mb mỗi nano giây);
  • 1−2−4 (10 Mb mỗi nano giây);

nên tốc độ truyền từ 1 đến 4 là 60 Mb mỗi nano giây, tức F1,4=60. Trong ví dụ này, ma trận tốc độ truyền F đầy đủ là:

F 1 2 3 4
1 0 60 60 60
2 60 0 60 60
3 60 60 0 90
4 60 60 90 0

DUT có ma trận tốc độ truyền mong muốn F. Nhiệm vụ của bạn là giúp họ chọn các dây cáp và cách nối N máy chủ để đạt được đúng ma trận tốc độ truyền F. Có thể có nhiều cấu hình cùng đạt được điều đó; chẳng hạn với ma trận trên, mạng gồm các dây cáp 3−4 (50), 1−2, 1−3, 1−4, 2−3, 2−4 (mỗi dây 20) cũng cho đúng ma trận F này.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T: số bộ test. Tiếp theo là T bộ test:

  • Mỗi bộ test bắt đầu bằng số nguyên N (1≤N≤200).
  • N dòng tiếp theo, mỗi dòng chứa N số nguyên mô tả ma trận F.
  • Dữ liệu đảm bảo Fu,v=Fv,u, Fu,u=0, 0≤Fu,v≤1000000.
  • Tổng N của mọi bộ test không vượt quá 1000.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng Case #t: YES hoặc Case #t: NO (t là số thứ tự bộ test, bắt đầu từ 1) tùy theo có thể hay không thể đạt được ma trận tốc độ truyền F. Nếu có thể, N dòng tiếp theo mô tả cấu hình của bạn: số thứ v trên dòng thứ u là Cu,v. Bạn phải đảm bảo Cu,v=Cv,u, Cu,u=0 và 0≤Cu,v≤1000000 (Cu,v=0 nghĩa là không có dây cáp giữa u và v).

Nếu có nhiều cấu hình thỏa mãn, in ra một cấu hình bất kỳ.

Ràng buộc

  • 1≤N≤200, tổng N không vượt quá 1000.
  • Fu,v=Fv,u, Fu,u=0, 0≤Fu,v≤106.

Ví dụ

Input Output Giải thích
2
3
0 1 2
1 0 4
2 4 0
4
0 60 60 60
60 0 60 60
60 60 0 90
60 60 90 0
Case #1: NO
Case #2: YES
0 60 60 0
60 0 0 0
60 0 0 90
0 0 90 0
Ở bộ test thứ nhất, F1,2=1 nhưng F1,3=2 và F3,2=4: dữ liệu có thể đi từ 1 đến 3 rồi từ 3 đến 2 với tốc độ 2, nên không thể có F1,2=1. Ở bộ test thứ hai, cấu hình được in gồm các dây 1−2 (60), 1−3 (60), 3−4 (90). Cấu hình trong đề gốc (1−2, 1−3, 2−3 mỗi dây 30 và 3−4 dây 90) cũng đúng.
4
1
0
2
0 0
0 0
2
0 5
5 0
3
0 0 5
0 0 5
5 5 0
Case #1: YES
0
Case #2: YES
0 0
0 0
Case #3: YES
0 5
5 0
Case #4: NO
Ví dụ bổ sung (không có trong đề gốc). Bộ test thứ tư không thể đạt được: nếu máy chủ 1 và 2 đều truyền được tới máy chủ 3 thì chúng truyền được cho nhau qua máy chủ 3, nên F1,2 không thể bằng 0.

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