trang chủ / đề bài / icpcwf11_h

Đào mỏ

Đề bài

Mô tả

John Digger là chủ một mỏ illudium phosdex lớn. Mỏ gồm nhiều đường hầm gặp nhau tại các nút giao lớn. Khác với một số chủ mỏ, Digger thật sự quan tâm đến sự an toàn của công nhân và lo lắng về cách bố trí của mỏ. Cụ thể, ông sợ rằng có thể có một nút giao mà nếu bị sập sẽ cắt rời công nhân ở một khu vực của mỏ khỏi những công nhân khác (illudium phosdex, như ai cũng biết, rất không ổn định). Để phòng ngừa, ông muốn xây các giếng thoát hiểm đặc biệt từ các nút giao lên mặt đất. Ông có thể xây một giếng thoát hiểm ở mỗi nút giao, nhưng Digger cũng không quan tâm đến công nhân nhiều đến thế. Thay vào đó, ông muốn xây ít giếng thoát hiểm nhất sao cho dù nút giao nào bị sập, mọi công nhân sống sót sau vụ sập đều có đường đi lên mặt đất.

Hãy viết chương trình tính số giếng thoát hiểm ít nhất và tổng số cách xây số giếng thoát hiểm ít nhất đó.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên dương N là số đường hầm của mỏ. Tiếp theo là N dòng, mỗi dòng chứa hai số nguyên phân biệt s và t là số hiệu của hai nút giao được nối bởi một đường hầm. Các nút giao được đánh số liên tiếp bắt đầu từ 1. Mỗi cặp nút giao được nối bởi nhiều nhất một đường hầm. Các đường hầm của mỗi mỏ tạo thành một khối liên thông (tức là từ một nút giao bất kỳ có thể đi đến mọi nút giao khác).

Sau bộ test cuối cùng là một dòng chứa một số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test, theo sau là số giếng thoát hiểm ít nhất cần xây cho hệ thống đường hầm và tổng số cách xây số giếng thoát hiểm đó, theo đúng định dạng của ví dụ. Đảm bảo kết quả nằm trong phạm vi số nguyên có dấu 64 bit.

Ràng buộc

  • 1≤N≤5·104.
  • s≠t; mỗi cặp nút giao được nối bởi nhiều nhất một đường hầm; các nút giao được đánh số liên tiếp từ 1; đồ thị liên thông.

Ví dụ

Input Output Giải thích
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Case 1: 2 4
Case 2: 4 1
Bộ 1: nút giao 4 chỉ nối với nút 1, nếu nút 1 sập thì công nhân ở nút 4 bị cô lập nên phải có giếng ở nút 4; một giếng thứ hai đặt ở một trong các nút 2,3,5,6 (khi nút 4 sập, công nhân còn lại dùng giếng này). Có 1·4=4 cách. Bộ 2: mỏ là một cây, phải có giếng ở mỗi lá 4,5,6,7.
4
1 2
2 3
3 4
4 1
1
1 2
5
1 2
2 3
3 1
3 4
4 5
0
Case 1: 2 6
Case 2: 2 1
Case 3: 2 2
Bộ 1: chu trình 4 nút không có nút giao nào mà khi sập làm mất liên thông, nhưng một giếng là không đủ vì chính nút có giếng có thể sập; cần 2 giếng ở hai nút bất kỳ, (42)=6 cách. Bộ 2: hai nút, mỗi nút một giếng. Bộ 3: một giếng ở nút 5 và một giếng ở nút 1 hoặc 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