Mafia
Time limit2sMemory limit128 MB
Given a graph of tollgates and highways, choose a minimum-cost set of intermediate tollgates whose removal disconnects the start from the destination, solved via vertex-split min-cut/max-flow.
Problem
A mafia group is trying to move through a highway network from a starting tollgate to a destination tollgate. The network consists of n tollgates and m bidirectional highways. Cars cannot enter or leave in the middle of a highway, so every route must pass only through tollgates and highways.
Each tollgate has an occupation cost. You may occupy some tollgates, except for the starting tollgate and the destination tollgate, so that the group cannot travel from the start to the destination without passing through an occupied tollgate.
Find the tollgates to occupy while minimizing the total occupation cost.
Input
The first line contains the number of tollgates n and the number of highways m. (1 <= n <= 200, 1 <= m <= 20,000) Tollgates are numbered from 1 to n.
The second line contains the starting tollgate s and the destination tollgate t. The next n lines contain the occupation costs of tollgates 1 through n, one per line. Each cost is a positive integer not greater than 10,000,000.
The final m lines each contain two tollgates a and b connected by a highway. Every highway can be traveled in both directions.
Output
Print, in increasing order on one line, the numbers of the tollgates selected with minimum total occupation cost.
If no tollgate needs to be printed, print an empty line.