11613 - Acme Corporation

[greve]

Can anybody explain to me how the answer for the case in the sample input is 2? I have been looking at the problem for a while now, and it seems to me that it can be solved using max-cost max-flow, but it seems a bit pointless to try if one cannot understand the sample output.

[greve]

I contacted the problem author, and he told me that there was an error in the sample output. It is supposed to be 20 (not 2), but it will probably be corrected soon. Anyway, the problem can be solved using discrete ternary search and max-cost max-flow, but my solution is quite slow, so maybe there is a better solution.

[baodog]

Hi,

Thanks! You are solving min cost flow using ternary search + min cost max flow .. A primal dual or cycle cancelation solution might be faster.

[greve]

You are right - I am solving min cost flow. I have also been told that it can be done with a single run of min-cost max-flow using the successive shortest path method, so that should speed up my solution significantly.

[baodog]

Actually, I got ac in 0.5 seconds, using just min cost max flow.
I use a very simple trick to conver min cost flow to min cost max flow
-- just connect source to sink with infinite capacity and 0 cost.
This allows X to be "thrown away" before been produced. Then at max flow it's fine.

[shiplu_1320]

Need some input output.