P2738 [USACO4.1] Fence Loops

The fences on Farmer Brown's pasture have gotten out of control. They have been divided into segments that are $1\sim 200$ feet long. Two segments can be connected only at their endpoints, and sometimes more than two fences meet at a given endpoint. As a result, the fences form a network that partitions Brown's pasture. Brown wants to restore the pasture to its original state; to do so, he first needs to know which region has the smallest perimeter. Brown labeled each fence segment from $1$ to $N$ ($N=$ the total number of segments). For each segment, he knows: - The length of the segment; - The labels of the segments connected to one endpoint of this segment; - The labels of the segments connected to the other endpoint of this segment. Fortunately, no fence connects to itself. Given data describing how the fences partition the pasture, write a program to compute the smallest perimeter among all regions. For example, fences labeled $1\sim 10$ form the configuration shown below (numbers indicate fence labels): ```plain 1 +---------------+ |\ /| 2| \7 / | | \ / | +---+ / |6 | 8 \ /10 | 3| \9 / | | \ / | +-------+-------+ 4 5 ``` In the figure above, the region with the smallest perimeter is formed by fences $2, 7, 8$.

The first line contains an integer $N$ ($1 \leq N \leq 100$). Lines $2$ through $3\times N+1$ describe $N$ groups, three lines per group: - The first line of each group has $4$ integers: $s$, the label of this fence segment ($1\le s\le N$); $L_s$, the length of this segment ($1\le L_s\le255$); $N1_s$, the number of neighboring fences at one endpoint ($1\le N1_s\le 8$); and $N2_s$, the number of neighboring fences at the other endpoint ($1\le N2_s\le 8$). - The second line of each group has $N1_s$ integers: the labels of the fences adjacent at one endpoint. - The third line of each group has $N2_s$ integers: the labels of the fences adjacent at the other endpoint.

Output a single line containing one integer, the minimum perimeter.

This statement is translated from NOCOW. USACO Training Section 4.1. Translated by ChatGPT 5