trang chủ / đề bài / icpc21_mn_a

Hệ thống đám mây

Đề bài

Mô tả

Trường Đại học Khoa học Tự nhiên TP. Hồ Chí Minh vừa xây dựng một hệ thống điện toán đám mây mới để chạy các thí nghiệm cho những nghiên cứu liên quan đến học sâu.

Hệ thống gồm N máy chủ (đánh số từ 1 đến N). Mỗi cặp máy chủ được nối với nhau bởi nhiều nhất 1 sợi cáp (có thể không có sợi nào). Sợi cáp nối máy chủ u và máy chủ v có khả năng truyền 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.

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

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

nên tốc độ truyền từ 1 đến 4 là 60 megabit mỗi nano giây, tức là F1,4=60.

Cho cấu hình của mạng và khả năng truyền của các sợi cáp, nhiệm vụ của bạn là tính ma trận F.

Dữ liệu vào

  • Dòng đầu tiên chứa T là số bộ dữ liệu. Tiếp theo là T bộ dữ liệu.
  • Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa N là số máy chủ trong mạng (N≤200).
  • N dòng tiếp theo, mỗi dòng chứa N số nguyên: số thứ v trên dòng thứ u là Cu,v (0≤Cu,v≤10000; Cu,v=0 nghĩa là không có cáp nối u và v).

Dữ liệu đảm bảo Cu,v=Cv,u và Cu,u=0. Tổng N của mọi bộ dữ liệu không vượt quá 1000.

Dữ liệu ra

Với bộ dữ liệu thứ t, in ra dòng "Case #t:", sau đó in ra N dòng là ma trận F kích thước N×N (quy ước Fu,u=0).

Ràng buộc

  • 1≤N≤200, tổng N không vượt quá 1000.
  • 0≤Cu,v≤10000, Cu,v=Cv,u, Cu,u=0.

Ví dụ

Input Output Giải thích
2
4
0 50 20 30
50 0 0 10
20 0 0 70
30 10 70 0
4
0 10 0 0
10 0 0 0
0 0 0 10
0 0 10 0
Case #1:
0 60 60 60
60 0 60 60
60 60 0 90
60 60 90 0
Case #2:
0 10 0 0
10 0 0 0
0 0 0 10
0 0 10 0
Bộ thứ nhất là mạng trong ví dụ của đề: F1,4=60; giữa 3 và 4 có thể truyền 70 trực tiếp và thêm 20 qua máy chủ 1, nên F3,4=90. Trong bộ thứ hai, {1,2} và {3,4} không nối với nhau.
2
1
0
3
0 5 0
5 0 7
0 7 0
Case #1:
0
Case #2:
0 5 5
5 0 7
5 7 0
Một máy chủ duy nhất; đường 1−2−3 bị giới hạn bởi cáp 1−2.

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