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

Bài tập huấn luyện: Chọn đường

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


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


Đề bài


Một tình báo viên được tung vào một vùng có một hệ thống giao thông gồm N nút đánh số 1..N, 1 <= N <= 200. Giữa một số cặp nút khác nhau có các đoạn đường đi hai chiều, hai đoạn đường đi khác nhau nếu không gặp nhau tại các điểm không là nút nhưng giữa hai cặp nút có thể có nhiều đoạn đường khác nhau nối chúng. Vì điều kiện hoạt động khó khăn, mỗi ngày anh ta chỉ dò tìm được một đoạn đường mới của hệ thống do đó hàng ngày anh ta phải báo về trung tâm một tập đoạn đường thoả mãn yêu cầu:

Bảo đảm sự đi lại giữa hai nút bất kỳ và có tổng độ dài nhỏ nhất   (*)

Tập đoạn đường này có thể thay đổi sau khi biết được thông tin về một đoạn đường mới hoặc vẫn như ngày hôm trước.

Bạn nhận được file CD.INP trong đó dòng thứ nhất ghi hai số N và W, W là số ngày hoạt động của tình báo viên, W<= 6000; trong W dòng tiếp theo, dòng thứ i ghi ba số nguyên X, Y, Z với ý nghĩa, ngày thứ I anh ta phát hiện được đoạn đường mới nối hai nút X, Y có độ dài Z, 1 <= Z <=10000.

Đóng vai trò tình báo viên, với mỗi thông tin về đoạn đường mới phát hiện trong ngày thứ I, ghi ra dòng thứ I của file CD.OUT như sau: nếu không chọn được tập đường thoả mãn yêu cầu (*), ghi số -1, nếu chọn được tập đoạn đường thoả mãn yêu cầu (*), ghi tổng độ dài các đoạn đường chọn ra.

Ví dụ:

CD.INP CD.OUT
4 6

1 2 10

1 3 8

3 2 3

1 4 3

1 3 6

2 1 2

-1

-1

-1

14

12

8

 

 


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ả

Chuyên mục

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ê

  • 254,200 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: