Đà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 là số đường hầm của mỏ. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên phân biệt và 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ừ . 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ố .
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 bit.
Ràng buộc
- .
- ; 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ừ ; đồ 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 chỉ nối với nút , nếu nút sập thì công nhân ở nút bị cô lập nên phải có giếng ở nút ; một giếng thứ hai đặt ở một trong các nút (khi nút sập, công nhân còn lại dùng giếng này). Có cách. Bộ 2: mỏ là một cây, phải có giếng ở mỗi lá . |
| 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 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 giếng ở hai nút bất kỳ, cách. Bộ 2: hai nút, mỗi nút một giếng. Bộ 3: một giếng ở nút và một giếng ở nút hoặc . |
Bình luận