Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
REFORM - VOI 2015 Day 1 - Kế hoạch cải tổ |
Mạng giao thông của thành phố NВ có n nút giao thông và m đoạn đường phố hai chiều nối các nút giao thông. Các nút giao thông được đánh số từ 1 đến n. Các đoạn đường phố được đánh số từ 1 đến m. Mạng giao thông của thành phố có tính chất sau đây:
- Giữa hai nút giao thông bất kỳ có không quá một đoạn đường phố nối chúng;
- Không có đoạn đường phố nào nối một nút giao thông với chính nó.
Vấn đề giao thông là thách thức với chính quyền thành phố từ nhiều năm. Với mong muốn đảm bảo việc đi lại thuận lợi hơn cho người dân, chính quyền thành phố quyết định tiến hành cải tổ mạng giao thông, trước hết nhằm đảm bảo có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại. (Lưu ý là mạng giao thông trước khi cải tổ có thể không đảm bảo yêu cầu này.) Tuy nhiên, do hạn hẹp về nguồn kinh phí, trước mắt kế hoạch cải tổ chỉ có thể bao gồm 2 công việc:
- Loại bỏ một đoạn đường phố hiện có khỏi mạng giao thông;
- Xây dựng một đoạn đường chưa từng có trước đó nối hai nút giao thông khác nhau.
Đồng thời, sau khi thực hiện cải tổ, mạng giao thông phải đảm bảo có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại.
Yêu cầu: Giúp chính quyền thành phố xác định xem có bao nhiêu cách khác nhau để thực hiện kế hoạch cải tổ thỏa mãn các yêu cầu đặt ra. (Hai kế hoạch cải tổ là khác nhau nếu có ít nhất một trong hai đoạn đường được lựa chọn loại bỏ hay xây dựng mới là khác nhau.)
Dữ liệu vào:
- Dòng đầu tiên chứa hai số nguyên n và m;
- Dòng thứ i trong số m dòng tiếp theo chứa hai số nguyên ui và vi (1 ≤ ui, vi ≤ n, ui ≠ vi) là chỉ số của hai nút giao thông được nối bởi đoạn đường i (i = 1, 2, …, m).
Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
- Ghi ra một số nguyên là số cách thực hiện kế hoạch cải tổ mạng giao thông thỏa mãn các yêu cầu đặt ra.
Ví dụ:
Dữ liệu vào: (ví dụ 1)
4 4
1 2
2 3
2 4
3 4
Dữ liệu ra: (ví dụ 1)
8
Hình vẽ minh họa: (ví dụ 1)
Dữ liệu vào: (ví dụ 2)
7 5
1 2
3 4
5 6
5 7
6 7
Dữ liệu ra: (ví dụ 2)
0
Hình vẽ minh họa: (ví dụ 2)
Được gửi lên bởi: | VOJ Team |
Ngày: | 2015-01-13 |
Thời gian chạy: | 1s |
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 JS-MONKEY PERL6 PYPY RUST SED |
Nguồn bài: | VOI15 day 1 |
hide comments
|
|||||||||
2016-10-04 15:07:05
cút hết ra cho anh thể hiện |
|||||||||
2016-09-30 03:39:07 minhsn
trau k ac dau may pn |
|||||||||
2016-09-28 18:48:38
bao đóng trên đồ thị 2 phía |
|||||||||
2016-09-28 16:51:28 xin đừng quên tôi
bài hay |
|||||||||
2016-08-01 16:56:09
làm đúng rồi, mà không đọc cmt của Nguyễn Vĩnh Thịnh về giới hạn, nên sub tận 6 lần :'( |
|||||||||
2016-06-15 12:06:56 Lương Ðức Tuấn Ðạt
Tham khảo thuật toán và code tại: yeulaptrinh.pw/268/reform-spoj/ |
|||||||||
2016-04-19 15:20:22
Viết sai tên biến be bét cũng được 66... |
|||||||||
2015-12-11 06:11:45 ChienTran
1 phát AC, cứ tưởng bài 2 dễ hơn |
|||||||||
2015-12-06 12:02:51 Ðặng Phương Tân
int64 hết mới AC :D |
|||||||||
2015-12-02 17:29:34 Thắng Ðam Mê
làm bài sai 1 đống lỗi luôn làm phải sub nhiều lần |