|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||38||29||28||75.676%|
The BAPC draws a large number of visitors to Amsterdam. Many of these people arrive at the train station, then walk from intersection to intersection through the streets of Amsterdam in a big parade until they reach the BAPC location.
A street can only allow a certain number of people per hour to pass through. This is called the capacity of the street. The number of people going through a street must never exceed its capacity, otherwise accidents will happen. People may walk through a street in either direction.
The BAPC organizers want to prepare a single path from train station to BAPC location. They choose the path with maximum capacity, where the capacity of a path is defined to be the minimum capacity of any street on the path. To make sure that nobody walks the wrong way, the organizers close down the streets which are incident1 to an intersection on the path, but not part of the path.
Can you write a program to help the organizers decide which streets to block? Given a graph of the streets and intersections of Amsterdam, produce the list of streets that need to be closed down in order to create a single maximum-capacity path from the train station to the BAPC. The path must be simple, i.e. it may not visit any intersection more than once.
1An edge is incident to a vertex if the vertex is an endpoint of the edge.
You may assume the following:
Output a single line containing a list of space separated street numbers that need to be blocked in order to create a single maximum-capacity path from train station to BAPC. Sort these street numbers in increasing order.
If no street must be blocked, output the word “none” instead.
7 10 0 1 800 1 2 300 2 3 75 3 4 80 4 5 50 4 6 100 6 1 35 0 6 10 0 2 120 0 3 100
0 2 4 6 7 8
4 4 0 1 10 1 2 50 0 3 30 1 3 20
4 3 0 1 10 1 2 20 2 3 30
Figure 2: Illustration of the first example input.