Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
NKBAS - Trung tâm bảo hành |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkbas
Một công ty máy tính bán hàng cho các khách hàng ở N thành phố (3 ≤ N ≤ 35) đánh số từ 1 đến N. Có M đoạn đường, mỗi đoạn đường nối hai thành phố nào đó. Công ty muốn mở các trung tâm bảo hành đặt tại một số thành phố này sao cho mỗi thành phố hoặc là có trung tâm bảo hành đặt tại nó hoặc có trung tâm bảo hành đặt ở thành phố có đoạn đường nối trực tiếp với nó.
Yêu cầu: Hãy xác định xem công ty cần mở ít nhất bao nhiêu trung tâm để đáp ứng điều kiện trên.
Dữ liệu
- Dòng đầu tiên chứa hai số N, M cách nhau bởi dấu cách.
- Mỗi dòng trong số M dòng tiếp theo chứa hai số nguyên là các chỉ số của các đầu mút của một trong số M đoạn đường.
Kết qủa
Ghi ra số lượng trung tâm bảo hành ít nhất cần mở.
Hạn chế
- Có 40% số test có 3 ≤ N ≤ 15.
Ví dụ
Dữ liệu: 8 12 1 2 1 6 1 8 2 3 2 6 3 4 3 5 4 5 4 7 5 6 6 7 6 8 Kết qủa 2
Được gửi lên bởi: | Jimmy |
Ngày: | 2008-01-04 |
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ừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED |
Nguồn bài: | VM10 (Luyện tập) - Nguồn: Bulgarian OI 99 |
hide comments
|
|||||
2021-01-05 17:58:05
oops |
|||||
2019-03-01 10:26:12
Good problem! %%$ |
|||||
2018-06-01 14:02:49
bài này làm sao để ac vậy mn? mình làm đến 60đ thôi |
|||||
2016-10-29 15:08:55
dsu |
|||||
2016-10-12 19:34:21
ngồi 4 tiếng 40đ đề bài như cái đb ( đầu bài ) |
|||||
2016-03-21 03:28:10
. Last edit: 2016-03-21 04:11:54 |
|||||
2016-03-20 17:59:33
test 1 là test đầu tiên sai và bạn dc 20 điểm :v |
|||||
2016-03-20 17:55:39
"20 WA-test-1" là lỗi gì ạ |
|||||
2013-06-03 03:32:15 Ðặng Duy Thảo
cho mình hỏi 60 WA-test-1 là gì vậy, nộp bài xong nó báo cái này mà không hiểu lắm |
|||||
2012-09-19 09:33:57 ان منتدى
cai na`y 2 chie`u |