Help on a MCMF problem — ADAGROW

Правка en1, от filippos, 2022-04-22 01:37:44

Hi everyone, as mentioned in the title I have been recently trying to solve ADAGROW on SPOJ, but my best attempt was to model the solution as Min Cost Max Flow problem, with a graph made of $$$~10^6$$$ edges.

The total flow that can be sent is only $$$K \le 20$$$, but my solution was still far from fitting into the TL. I realized that some of edges could be skipped and that if the input was random skipping those edges would've made the network small enough to pass — this way, I managed to AC the problem.

The worst case of my solution still has $$$~N^2/4$$$ edges, so I was wondering if anyone had tips on how else to model it so that the number of edges is always something reasonable.

Thanks!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский filippos 2022-04-22 09:05:35 29 Tiny change: '^6$ edges [$O(N^2)$]. \n\nThe ' -> '^6$ edges ( $O(N^2)$ ). \n\nThe '
en1 Английский filippos 2022-04-22 01:37:44 778 Initial revision (published)