Spijuni
레이팅 미적용의견: 0
\(7^{th}\) round (Croatian Olympiad in Informatics), April \(6^{th}\), 2013
You are \(M\), the head of the intelligence agency which employs N spies with codenames from 1 to N.
Each of the spies has been assigned a different country and obtained an important piece of information
there. Your task is the following:
1. Organize meetings between some of the spies. In each meeting, exactly two spies meet and
exchange all information that they have obtained themselves or learned from other spies in
previous meetings. Organizing a t\(op-se\)cret meeting between two spies in different countries is
difficult, so each potential meeting has a price.
2. After all the meetings have concluded, select a subset of spies and send them together on the
wor\(ld-sa\)ving (and wom\(an-ro\)mancing) assignment. Sending a spy k on the assignment costs M_{k}.
For the assignment to succeed, it is important that the spies together know all the information
obtained by the remaining spies.
Find the minimum total price of preparing and executing this assignment.
In test data with \(N \le 30\), which is worth a total of 40 points, it will be optimal to send at most four
spies on the assignment.
In test data worth a total of 50 points, all prices of sending spies on assignment are equal.
\(7^{th}\) round (Croatian Olympiad in Informatics), April \(6^{th}\), 2013
The first line of input contains the positive integer N, the number of spies (\(2 \le N \le 1000\)).
Each of the following N lines contains N positive integers not exceeding \(10^{6}\). The number in row k
and column m represents the price of a meeting between spies k and m and, of course, equals the
number in row m and column k (for \(k = m\) the number will be 0).
The following line contains N positive integers M_{k} (\(1 \le M_{k} \le 10^{6}\)), the prices of sending each spy on
the assignment, in order for spies 1, 2, ..., N.
The first and only line of output must contain the required minimum total price.
3
0 6 9
6 0 4
9 4 0
7 7 7173
0 17 20
17 0 10
20 10 0
15 9 12345
0 3 12 15 11
3 0 14 3 20
12 14 0 11 7
15 3 11 0 15
11 20 7 15 0
5 10 10 10 1028Clarification of the first example: We will organize meetings between spies 1 and 2, then 2 and 3,
and send spy 2 on the assignment.
Clarification of the second example: We will organize a meeting between spies 2 and 3, and send
spies 1 and 2 on the assignment.
Clarification of the third example: We will organize meetings between spies 2 and 4, then 1 and 2,
then 3 and 5, and send spies 1 and 3 (or 1 and 5) on the assignment.
평가 및 의견
Spijuni
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Spijuni