网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Feb09]环绕大陆
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 14:10 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 14:10 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 14:10 |
输入文件 | surround.in | 输出文件 | surround.out |
Surround the Islands [Fatih Gelgi, 2008] Farmer John has bought property in the Caribbean and is going to try to raise dairy cows on a big farm composed of islands. Set in his ways, he wants to surround all the islands with fence. Each island in the farm has the shape of a polygon. He fences the islands one side at a time (between a consecutive pair of vertices) and proceeds clockwise around a given island with his fencing operations. Since he wants to fence all the islands, he must at some point travel to any other islands using a boat. He can start fencing at any vertex and, at any vertex he encounters, travel to some vertex on another island, fence all the way around it, and then IMMEDIATELY return back to the same vertex on the original island using the same path he traveled before. Each boat trip has a cost defined by a supplied matrix. The islands are described by a set of N (3 <= N <= 500) pairs of vertices V1,V2 (1 <= V1 <= N; 1 <= V2 <= N) although you must figure out how to assemble them into islands. The vertices are conveniently numbered 1..N. The cost of traveling by boat between each pair of vertices is given by a symmetric cost matrix whose elements fall in the range 0..1000. What is the minimum cost of surrounding the islands with the fence? PROBLEM NAME: surround INPUT FORMAT: * Line 1: A single integer: N * Lines 2..N+1: Each line describes an island's border with two space-separated integers: V1 and V2 * Lines N+2..2*N+1: Line i-N-1 contains N integers that describe row i of the cost matrix: Row_i SAMPLE INPUT (file surround.in): 12 1 7 7 3 3 6 6 10 10 1 2 12 2 9 8 9 8 12 11 5 5 4 11 4 0 15 9 20 25 8 10 13 17 8 8 7 15 0 12 12 10 10 8 15 15 8 8 9 9 12 0 25 20 18 16 14 13 7 12 12 20 12 25 0 8 13 14 15 15 10 10 10 25 10 20 8 0 16 20 18 17 18 9 11 8 10 18 13 16 0 10 9 11 10 8 12 10 8 16 14 20 10 0 18 20 6 16 15 13 15 14 15 18 9 18 0 5 12 12 13 17 15 13 15 17 11 20 5 0 22 8 10 8 8 7 10 18 10 6 12 22 0 11 12 8 8 12 10 9 8 16 12 8 11 0 9 7 9 12 10 11 12 15 13 10 12 9 0 INPUT DETAILS: 1 10 4 xxxxxxx x xxxxxxxxx xxxx 7 xxxxxxxxxxx 6 xxxxxxx xxxxxxxxxxx 11 xxxxxxxxxx 5 xxxxxxx xxx 3 12 xxxxxxx 2 xxxxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxxx xxxxxxxxxx 8 xxxxxxxxxx 9 The example describes three islands: {1,7,3,6,10}, {4,5,11} and {2,9,8,12}. The travel costs are provided as a matrix. For example, the travel cost from vertex 1 to 2 is 15. OUTPUT FORMAT: * Line 1: A single integer that specifies the minimum cost of building the fence SAMPLE OUTPUT (file surround.out): 30 OUTPUT DETAILS: There is more than one solution. One is: FJ starts from vertex 3 then 7 and stops at 1, travels to 11 followed by 4,5,11. He then returns back to 1, and travels to 12 followed by 2,9,8,12. Finally, he returns back to 1 and continues with 10,6,3,7. The costs are 8 * 2 = 16 for traveling from 1 to 11 and returning back, and 7 * 2 = 14 for traveling from 1 to 12 and back -- a total cost of 30.