1758. Which Pipes To Destroy
A DIRECTED network has n junctions and m pipes, pipe i running from u to
v with capacity c. Problem 1756 asks what the cheapest way to shut t off
from s COSTS. This asks which pipes to destroy.
Print how many pipes are in the answer, then their numbers as they appeared in the input, smallest first.
## The answer is pinned, because the cheapest set is usually not unique
1->2 cap 1, 2->3 cap 1 s=1 t=3
Destroying pipe 1 costs 1 and works; destroying pipe 2 costs 1 and works. So this problem asks for a particular one: take the cheapest split whose group 1 is SMALLEST, exactly as problem 1757 defines it, and destroy the pipes running from group 1 to group 2. In the example that is pipe 1 alone.
## The three things that have to be said
directed? yes. A pipe from group 2 back into group 1 is NOT destroyed
and costs nothing, and including it is the commonest error.
self-loops? allowed. Both ends are in the same group, so a self-loop is
never in the answer.
parallel pipes? allowed, and if one copy is in the answer every copy is,
because they share both endpoints. Pipe NUMBERS are asked
for precisely so the two copies can be told apart.
disconnected? allowed. The answer can be empty, and the sentinel None
exists so the second line is never blank.
## What most people try first
Collect every pipe that the finished flow fills to capacity. That is wrong, and here is the smallest case:
1->2 cap 1, 2->3 cap 1, 2->4 cap 1 s=1 t=3
The flow is 1, along 1->2->3. Both 1->2 and 2->3 end up full, so the
"every full pipe" rule names two pipes costing 2, when destroying 1->2 alone
costs 1 and finishes. Being full is necessary but nowhere near sufficient: the
pipe also has to run from the group the source can still reach to the group it
cannot.
The second attempt is every subset of pipes, 2^m, which at m = 500 is not a
number.
## The method
run Edmonds-Karp from s to t
search from s along residual capacity only; call what you reach group 1
for i in 0 .. m-1:
if eu[i] in group 1 and ev[i] not in group 1: report i
Scanning the input in order makes the report ascending with no sort.
## Cost
O(n * m * m) for the flow and O(m) for the scan, which at n = 100 and
m = 500 is 2.5 * 10^7. The flow total needs 64 bits because 500 pipes of
10^9 reach 5 * 10^11, well past 2147483647; the pipe numbers do not.
Constraints - `2 ≤ n ≤ 100` - `0 ≤ m ≤ 500` - `1 ≤ u, v ≤ n` - `1 ≤ c ≤ 1000000000` - `1 ≤ s, t ≤ n` and `s ≠ t`, so `n` is never 1 - self-loops and parallel pipes can occur, and both `u` to `v` and `v` to `u` may be present - the network may be disconnected, in which case the answer is empty
Input
The first line contains four integers n, m, s and t.
Each of the next m lines contains three integers u, v and c, a pipe from u to v of capacity c.
Output
Print the number of pipes in the answer on the first line. On the second line print their input numbers, counting from 1, separated by single spaces and smallest first. If the answer is empty print 0 and then the single word None, so the second line is never blank.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.