Xe tự hành - .:: HVAOnline ::.

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thảo luận hệ điều hành Windows

Xe tự hành

[Programming] Xe tự hành	21/03/2007 07:10:30 (+0700) \| #1 \| 48184

seraphpl
Member

Joined: 04/12/2006 19:52:12
Messages: 97
Location: xxx
Offline

Đội vệ sinh công cộng số 13 phụ trách quét rác đường phố cho một khu vực có N giao lộ và M đoạn đường. Để nâng cao hiệu quả công việc, ban phụ trách lên kế hoạch mua các xe tự hành quét rác sao cho:
. Mỗi đoạn đường sẽ chỉ được một xe tự hành quét rác.
. Xe tự hành quét rác các đoạn đường nói tiếp nhau, mỗi đoạn đường chỉ đi qua đúng một lần.
. Số lượng xe tự hành là ít nhất.
Hãy lập trình giúp Ban phụ trách Đội vệ sinh công cộng số 13.
Input : Cho bởi tập tin văn bản TUHANH.IN như sau:
. Dòng thứ nhất ghi hai số nguyên dương N, M.
. M dòng tiếp theo, mỗi dòng là 2 số u và v thể hiện tên giao lộ nói một đoạn đường.
Output : Cho bởi tập tin văn bản TUHANH.OUT như sau:
. Dòng thứ nhất ghi số nguyên dương K là số xe tự hành.
. Trong K dòng tiếp theo, mỗi dòng ghi hành trình của xe tự hành qua các giao lộ thể hiện các đoạn đường nói tiếp nhau mà xe đó sẽ quét rác.

- Em nghĩ là dùng thuật toán Floy để tính số đoạn đường dài nhất từ 1 đỉnh đến đỉnh khác (cho trọng số 1 cạnh là 1), ban đầu lấy đoạn đường dài nhất, đi theo đoạn đường đó, xóa bỏ những đoạn đã đi qua, tạo ra được 1 đồ thị mới, từ đồ thị mới lặp lại cho đến khi không còn đoạn đường nào. Vét hết rồi so sánh xem lần nào có số lượng xe tự hành là ít nhất, chọn cách đi đó.
- Cách này làm hơi lâu, mong mọi người giúp em cách tốt hơn.
Xin cám ơn.

Go to:

Users currently in here
1 Anonymous