[USACO09FEB] Surround the Islands S

**【题目描述】** Farmer John 在加勒比海购置了一片地产，准备在由一系列岛屿组成的农场上养奶牛。 出于他的意愿，他要把所有的岛屿都用篱笆围上。 每个岛都是多边形的。每一次，FJ 会给多边形的一个边（即相邻的两个顶点之间）装上篱笆。对于整个岛屿，他会按照顺时针顺序装上篱笆。由于他想要给所有的岛屿都装上篱笆，某些时候，他必须从一个岛屿坐船到另一个岛屿去。 FJ 可以从任何一个顶点开始装篱笆，也可以从任何一个顶点坐船到另一个岛的某个顶点上，从这个顶点开始把该岛屿的篱笆全都装好，然后**马上**坐船原路返回。保证任意两个顶点间都有航线。在任意两个顶点之间坐船的费用会在一个矩阵中给出。 所有的岛屿由给定的 $N$ 对顶点 $V_1$，$V_2$ 描述（即：给定顶点 $V_1$ 与 $V_2$ 相邻）。每个顶点具体属于哪个岛屿**不会**在输入中给出。所有顶点由 $1$ 到 $N$ 标号。 在顶点间坐船旅行的费用由一个 $N \times N$ 的矩阵给出。保证两个岛屿间两个方向的旅行费用相等且不会超过 $1000$。 请求出 FJ 把篱笆装完所需要的最小花费。 **【输入格式】** 第 $1$ 行：包含一个整数 $N$，含义见题目描述。 第 $2$ 至第 $N+1$ 行：每行包含两个整数 $V_1$ 和 $V_2$，表示这两个顶点在同一个岛屿上且相邻。 第 $N+2$ 行至第 $2N+1$ 行：每行包含 $N$ 个整数，第 $i-N-1$ 行的第 $j$ 个整数表示从 $i$ 号顶点坐船到第 $j$ 号顶点的花费。 **【输出格式】** 一行一个整数，表示 FJ 把篱笆装完所需要的最小花费。 **【说明/提示】** 对于所有数据，保证： + $3 \leq n \leq 500$ + $1 \leq V_1,V_2 \leq N$ + 任意两个顶点之间的旅行花费 $\leq 1000$

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?

\* 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

\* Line 1: A single integer that specifies the minimum cost of building the fence

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 

30 

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. 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.