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 roughly $$$10^6$$$ edges — $$$O(N^2)$$$.
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!