search

kth-competitive-programming / kactl

KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp)
2.68k stars 711 forks source link

Fix a bug of MinCostMaxFlow.h #263

Open tht2005 opened 1 month ago

tht2005 commented 1 month ago

Fix a bug that occur when maxflow function is called multiple times from different source vertices.

simonlindholm commented 1 month ago

It's enough to set par[s] = NULL at the start of maxflow, right? Can you modify the stress test to cover this case?

tht2005 commented 3 weeks ago

I add tests for this case.

tht2005 commented 2 weeks ago

It's enough to set par[s] = NULL at the start of maxflow, right? Can you modify the stress test to cover this case?

can you review my code

simonlindholm commented 2 weeks ago

NULL -> 0 to save a few chars. For the test, it doesn't actually check that maxflow returns the correct result, only that it doesn't crash. Can you check that too? E.g. test it by doing "construct graph. pick random a,b,c,d. compute e = maxflow(a,b), f = maxflow(c,d). set up the same maxflow instance again. compute f' = maxflow(c, d), e' = maxflow(a, b). check that e = e', f = f'."