trang chủ / đề bài / icpcwf18_k

Không dây thay cho cáp quang

Đề bài

Mô tả

Một công nghệ truyền thông không dây mới với băng thông không giới hạn vừa được thử nghiệm và chứng minh là có thể thay thế mạng truyền thông cáp quang hiện tại, vốn đang chật vật theo kịp sự tăng trưởng lưu lượng. Bạn được giao nhiệm vụ quyết định cách bố trí mạng truyền thông mới.

Mạng truyền thông hiện tại gồm một tập các nút (dùng để định tuyến tin nhắn) và các đường cáp quang, mỗi đường nối hai nút khác nhau. Với mỗi cặp nút, có ít nhất một cách (nhưng có thể nhiều hơn, để tăng băng thông) đi dọc theo các đường cáp quang từ nút này tới nút kia.

Mạng mới sẽ không có cáp quang. Thay vào đó, nó có các liên kết không dây, mỗi liên kết nối hai nút. Các liên kết này có băng thông không giới hạn nhưng rất đắt, vì vậy người ta quyết định xây càng ít liên kết càng tốt mà vẫn đảm bảo kết nối: với mỗi cặp nút phải có đúng một cách đi giữa chúng dọc theo các liên kết không dây.

Hơn nữa, bạn phát hiện ra rằng mỗi nút được chế tạo để phù hợp với một số lượng kết nối nhất định. Với mỗi nút, nếu nó được nối với số liên kết khác với số đường cáp quang nối tới nó hiện nay, nút đó sẽ phải được tổ chức lại, và việc này rất tốn kém.

Nhiệm vụ của bạn là thiết kế mạng mới sao cho giữa mỗi cặp nút có đúng một đường đi, đồng thời số nút có số kết nối khác với mạng ban đầu là nhỏ nhất.

Hình dưới đây minh họa ví dụ thứ nhất. Mạng cáp quang ban đầu (giữa nút 1 và nút 2 có hai đường cáp):

graph base=0
7 11
0 1
0 2
0 5
0 6
1 3
2 4
1 2
1 2
1 5
2 6
5 6

Một lời giải có thể có. Số liên kết thay đổi ở ba nút 1, 2 và 5 (tô đỏ):

graph base=0
7 6
0 1
0 2
0 5
0 6
6 3
6 4
highlight red 1 2 5
highlight green 0 3 4 6

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m: số nút và số đường cáp quang của mạng hiện tại. Các nút được đánh số từ 0 đến n−1.

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên phân biệt ai và bi, cho biết đường cáp quang thứ i nối nút ai với nút bi.

Dữ liệu đảm bảo với mỗi cặp nút luôn có ít nhất một đường đi nối chúng. Một cặp nút có thể được nối bởi nhiều hơn một đường cáp quang.

Dữ liệu ra

Dòng đầu tiên in số nút nhỏ nhất mà số liên kết nối tới nó phải thay đổi.

Bắt đầu từ dòng tiếp theo, in một mạng kết nối theo cùng định dạng với dữ liệu vào: một dòng chứa số nút (bằng n của dữ liệu vào) và số liên kết không dây, sau đó mỗi dòng mô tả một liên kết bằng hai số hiệu nút. Nếu có nhiều cách bố trí thỏa mãn, in cách nào cũng được.

Ràng buộc

  • 2≤n≤104.
  • 1≤m≤105.
  • 0≤ai,bi≤n−1, ai≠bi.

Ví dụ

Input Output Giải thích
7 11
0 1
0 2
0 5
0 6
1 3
2 4
1 2
1 2
1 5
2 6
5 6
3
7 6
0 1
0 2
0 5
0 6
3 6
4 6
Mạng trong hình. Số kết nối ban đầu của các nút 0..6 là 4,5,5,1,1,3,3; trong mạng mới là 4,1,1,1,1,1,3, nên ba nút 1, 2, 5 thay đổi.
4 3
0 1
2 1
2 3
0
4 3
2 1
1 3
0 2
Mạng ban đầu đã là một cây (đường đi 0−1−2−3). Mạng mới là đường đi 0−2−1−3, mọi nút giữ nguyên số kết nối.

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