//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Đặt trung tâm phục vụ

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 1


Đề bài


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ệnt trên.

Dữ liệu: Vào từ file văn bản BAS.INP:

  • 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 quả: Ghi ra file văn bản BAS.OUT số lượng trung tâm bảo hành cần mở.

Ví dụ:

BAS.INP BAS.OUT
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

2

 

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,393 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: