Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 12thIOI第二天试题二
发信站: 哈工大紫丁香 (2001年06月14日15:38:25 星期四), 站内信件

Walls
PROBLEM
In a country, great walls have been built in such a way that every great wall
 connects exactly two towns. The great walls do not cross each other. Thus, t
he country is divided into such regions that to move from one region to anoth
er, it is necessary to
go through a town or cross a great wall. For any two towns A and B, there is
at most one great wall with one end in A and the other in B, and further, it
is possible to go from A to B by always walking in a town or along a great wa
ll. The input format
implies additional restrictions.
There is a club whose members live in the towns. In each town, there is only
one member or there are no members at all. The members want to meet in one of
 the regions (outside of any town). The members travel riding their bicycles.
 They do not want to
enter any towns, because of the traffic, and they want to cross as few great
walls as possible, as it is a lot of trouble. To go to the meeting region, ea
ch member needs to cross a number (possibly 0) of great walls. They want to f
ind such an optimal
region that the sum of these numbers (crossing-sum, for short) is minimized.
                Figure 1                                        Figure 2
The towns are labeled with integers from 1 to N, where N is the number of tow
ns. In Figure 1, the labeled nodes represent the towns and the lines connecti
ng the nodes represent the great walls. Suppose that there are three members,
 who live in towns 3,
6, and 9. Then, an optimal meeting region and respective routes for members a
re shown in Figure 2. The crossing-sum is 2: the member from town 9 has to cr
oss the great wall between towns 2 and 4, and the member from town 6 has to c
ross the great wall
between towns 4 and 7.
You are to write a program which, given the towns, the regions, and the club
member home towns, computes an optimal region and the minimal crossing-sum.
INPUT
The input file name is WALLS.IN. The first line contains one integer: the num
ber of regions M, 2￡M￡200. The second line contains one integer: the number
 of towns N, 3￡N￡250. The third line contains one integer: the number of cl
ub members L,
1￡L￡30, L￡N. The fourth line contains L distinct integers in increasing or
der: the labels of the towns where the members live.
After that the file contains 2M lines so that there is a pair of lines for ea
ch region: the first two of the 2M lines describe the first region, the follo
wing two the second and so on. Of the pair, the first line shows the number o
f towns I on the
border of that region. The second line of the pair contains I integers: the l
abels of these I towns in some order in which they can be passed when making
a trip clockwise along the border of the region, with the following exception
. The last region is
the "outside region" surrounding all towns and other regions, and for it the
order of the labels corresponds to a trip in counterclockwise direction. The
order of the regions gives an integer labeling to the regions: the first regi
on has label 1, the
second has label 2, and so on. Note that the input includes all regions forme
d by the towns and great walls, including the "outside region".
OUTPUT
The output file name is WALLS.OUT. The first line contains one integer: the m
inimal crossing-sum. The second line contains one integer: the label of an op
timal region. There may be several different solutions for the region and you
r program needs to
output only one of them.
EXAMPLE INPUT AND OUTPUT
The following input and output files correspond to the example given in the t
ext.
             WALLS.IN                           WALLS.OUT

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]