| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PK11I - Paths in a Tree |
| English | Vietnamese |
Bạn được cho 1 cây (đồ thị liên thông không chu trình), và các cạnh của cây vì lí do nào đó đã được định chiều; nhiệm vụ của bạn là thêm vào ít nhất các đường đi đặc biệt trên cây này sao cho có thể đi từ mọi đỉnh đến mọi đỉnh khác. Luật của các đường đi đặc biệt như sau:
-
Một đường đi đặc biệt gồm một số cạnh và đỉnh liên tiếp trên cây.
-
Trong đường đi đặc biệt, các cạnh được định hướng ngược lại so với cạnh tương ứng trên cây.
-
Một đỉnh hoặc một cạnh chỉ được thăm tối đa 1 lần trong 1 đường đi đặc biệt.
-
Nhiều đường đi đặc biệt có thể có chung đỉnh hoặc canh.
Ví dụ, trong hình dưới đây là một cây, mũi tên đen mô tả cạnh và hướng của nó, hình tròn mô tả đỉnh. Ta có 2 đường đi đặc biệt. Một đường là 2-1-0 (mũi tên xanh lá cây), và đường kia là 3-1 (mũi tên xanh lam). Thay vì đường 3-1 ta có thể dùng 3-1-0. Bạn không thể dùng đường 1-3 hay 0-1-2 vì vi phạm luật thứ 2. Bạn không thể dùng đường 0-2 hoặc 2-3-0 vì vi phạm luật thứ 1.
Input
Dữ liệu bắt đầu bằng một số nguyên T (≤ 30), thể hiện số lượng bộ test.
Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên N (2 ≤ N ≤ 20000), mô tả số lượng đỉnh. Các đỉnh được đánh số từ 0 đến N-1. Mỗi dòng trong số N-1 dòng tiếp theo chứa 2 số nguyên u v (0 ≤ u, v < N, u ≠ v) mô tả một cạnh từ u đến v.
Output
Với mỗi bộ test, in ra chỉ số của bộ test và số lượng đường đi đặc biệt ít nhất cần thêm vào sao cho có thể đi lại giữa 2 đỉnh bất kỳ.
Example
Input:2
4
0 1
1 2
1 3
5
0 1
1 2
1 3
0 4
Output: Case 1: 2 Case 2: 3
| Được gửi lên bởi: | Race with time |
| Ngày: | 2012-07-25 |
| Thời gian chạy: | 0.906s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
| Nguồn bài: | ACM ICPC Regional Phuket 2011 |
hide comments
|
2012-08-06 14:31:03 T-7
Ok, em hiểu rồi :) |
|
|
2012-08-01 14:37:23 Nguyễn Mai Lan
Không được, thuật toán O(N) thì lẽ ra để 1s cũng AC :P |
|
|
2012-07-28 10:02:11 T-7
PS tăng time bài này lên 30s được ko? Coi như mỗi test 1s :P Last edit: 2012-07-28 10:02:45 |
RSS