//
you're reading...
00 - Chủ đề chung, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Chia nhóm

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


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


Đề bài


Xét một tập hợp gồm N phần tử (các phần tử được đánh số từ 1 đến N). Khi hoạt động, một phần tử có thể ảnh hưởng đến những phần tử khác. Để đo tính “độc lập” giữa 2 phần tử, người ta định nghĩa “khoảng cách” giữa 2 phần tử x, y là một số nguyên dương D(x, y) = D(y, x) sao cho khoảng cách này càng lớn thì độ độc lập giữa 2 phần tử càng cao. Trong một số công việc, người ta phải chia các phần tử thành những nhóm hoạt động riêng rẽ, vì vậy việc chia nhóm cần đảm bảo tính độc lập giữa các nhóm càng cao càng tốt. Độ “phân tách” D(A, B) giữa 2 nhóm A, B được định nghĩa như là khoảng cách nhỏ nhất giữa một phần tử của A và một phần tử của B:                        D(A, B) = Min {D(x, y), x thuộc  A, y thuộc B}

và độ “phân tách” D của một cách chia được gọi là độ phân tách của 2 nhóm “gần nhất” thuộc cách chia này:

D = Min {D(A, B)}

Bạn hãy viết một chương trình xác định độ phân tách lớn nhất có thể được, khi chia một tập hợp N phần tử với những khoảng cách đã cho, thành K nhóm.

Input File: NHOM.INP

– dòng đầu ghi 2 số N và K,

– dòng thứ i trong N dòng tiếp, i = 1, 2, …, N ghi N số D(i, j), j = 1, 2, …, N là khoảng cách giữa i và j. Chú ý D(i, j) = D(j, i); D(i, i) = 0.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu trắng.

Output File: NHOM.OUT, gồm 1 dòng ghi độ phân tách tìm được.

Giá trị giới hạn: N không quá 200, K lớn hơn 1 và nhỏ hơn N, các giá trị D(i, j) là những số nguyên không âm, nhỏ hơn 32768.

Thí dụ:

 

NHOM.INP NHOM.OUT
4  2                         3
0  4  5  2
4  0  3  6
5  3  0  3
2  6  3  0

 


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ê

  • 255,206 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: