6862 - 4.1.3 Fence Loops 篱笆回路

农夫布朗的牧场上的篱笆已经失去控制了.它们分成了 1~200 英尺长的线段.只有在线段的端点处才能连接两个线段,有时给定的一个端点上会有两个以上的篱笆.结果篱笆形成了一张网分割了布朗的牧场.布朗想将牧场恢复原样,出于这个考虑,他首先得知道牧场上哪一块区域的周长最小.

布朗将他的每段篱笆从1到N进行了标号(N=线段的总数).他知道每段篱笆的有如下属性:

 该段篱笆的长度

该段篱笆的一端所连接的另一段篱笆的标号 

该段篱笆的另一端所连接的另一段篱笆的标号

幸运的是,没有篱笆连接它自身.

对于一组有关篱笆如何分割牧场的数据,写一个程序来计算出所有分割出的区域中最小的周长. 

例如,标号 1~10 的篱笆由下图的形式组成(下面的数字是篱笆的标号):

15658390508747.png

上图中周长最小的区域是由 2,7,8 号篱笆形成的.

输入

15658518631852.png

输出

输出的内容为单独的一行,用一个整数来表示最小的周长。

样例

输入

10 
1 16 2 2 
2 7 
10 6 
2 3 2 2 
1 7 
8 3 
3 3 2 1 
8 2 
4 
4 8 1 3 
3 
9 10 5 
5 8 3 1 
9 10 4 
6 
6 6 1 2 
5 
1 10 
7 5 2 2 
 53
1 2 
8 9 
8 4 2 2 
2 3 
7 9 
9 5 2 3 
7 8 
4 5 10 
10 10 2 3 
1 6 
4 9 5

输出

12

来源

USACO

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题