Problem 2925 --4.1.3 Fence Loops

2925: 4.1.3 Fence Loops

上一题 正确率: $33.33\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $3$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 usaco

Description

The fences that surround Farmer Brown's collection of pastures have gotten out of control. They are made up of straight segments from 1 through 200 feet long that join together only at their endpoints though sometimes more than two fences join together at a given endpoint. The result is a web of fences enclosing his pastures. Farmer Brown wants to start to straighten things out. In particular, he wants to know which of the pastures has the smallest perimeter.

Farmer Brown has numbered his fence segments from 1 to N (N = the total number of segments). He knows the following about each fence segment:

  • the length of the segment 
  • the segments which connect to it at one end
  • the segments which connect to it at the other end.
Happily, no fence connects to itself.

Given a list of fence segments that represents a set of surrounded pastures, write a program to compute the smallest perimeter of any pasture. As an example, consider a pasture arrangement, with fences numbered 1 to 10 that looks like this one (the numbers are fence ID numbers): 

           1
   +---------------+
   |\             /|
  2| \7          / |
   |  \         /  |
   +---+       /   |6
   | 8  \     /10  |
  3|     \9  /     |
   |      \ /      |
   +-------+-------+
       4       5

The pasture with the smallest perimeter is the one that is enclosed by fence segments 2, 7, and 8.


Input

Line 1:  N (1 <= N <= 100)
Line 2..3*N+1: 

N sets of three line records:

  • The first line of each record contains four integers: s, the segment number (1 <= s <= N); Ls, the length of the segment (1 <= Ls <= 255); N1s (1 <= N1s <= 8) the number of items on the subsequent line; and N2sthe number of items on the line after that (1 <= N2s <= 8).
  • The second line of the record contains N1 integers, each representing a connected line segment on one end of the fence.
  • The third line of the record contains N2 integers, each representing a connected line segment on the other end of the fence.

Output

The output file should contain a single line with a single integer that represents the shortest surrounded perimeter.

Sample Input复制

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

Sample Output复制

12

推荐代码 查看2925 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC 淡意的温柔 596685 2020-06-12 17:24:00
第一挑战 淡意的温柔 596674 2020-06-12 17:22:04

赛题来源/所属竞赛 usaco training usaco Training

竞赛编号 竞赛名称 竞赛时间 访问比赛