In various places([1](https://mirror.codeforces.com/blog/entry/52714), [2](https://mirror.codeforces.com/blog/entry/52077?#comment-360923), ), people have talked about "Dinic's With Scaling" having $O(VElog(U))$ complexity, where U is the max edge capacity. However, in just as many places, people have cast doubt about this complexity or worried that this algorithm ends up being slower in practice([1](https://mirror.codeforces.com/blog/entry/52714?#comment-397827)[2](https://mirror.codeforces.com/blog/entry/52077?#comment-360949).↵
↵
I had the same doubts. In fact, a couple months ago I benchmarked Dinic's with scaling on some hard [test cases](https://mirror.codeforces.com/blog/entry/52714?#comment-397861) and thought that Dinic's with/without scaling performed similarly.↵
↵
As it turns out, I benchmarked it again yesterday and found that Dinic's with scaling definitely has significantly better asymptotic complexity (by a factor of V). ↵
↵
## Synthetic Benchmarking↵
I used the hard test case generator at 2 posted by [user:ko_osaga,2019-03-18] [here](https://mirror.codeforces.com/blog/entry/52714?#comment-397861). The one posted at 1 creates a graph with only V edges and moreover, doesn't work for me... Notably, given a V, it generates a graph with V nodes and $O(V^2)$ edges.↵
↵
The code I used was my own Dinic's implementation (originally from emaxx) found [here](https://gist.github.com/Chillee/ad2110fc17af453fb6fc3357a78cfd28). Notably, the `SCALING` variable toggles between Dinic's with scaling and without. It's a small change, as you can see.↵
↵
I ran the two code across a variety of input sizes, averaging across 10 runs, then taking the log of input size and times, plotting them in a  where blue is the runtime of Dinic's without scaling and orange is the runtime of Dinic's with scaling. Since the important thing to look at is the slope of the line, I normalized the lines to start at the same point.↵
↵
Fitting a linear regression to the points, we see that the slope of Dinic's without scaling is 3.204, while the slope of Dinic's with scaling is 1.93, which correspond to complexities of $O(V^3)$ and $O(V^2)$ respectively. ↵
↵
In terms of actual runtime, here are some numbers on specific sizes.↵
↵
## Benchmarking on Problems↵
There are 3 flow problems, I benchmarked on — [SPOJ FASTFLOW](https://www.spoj.com/problems/FASTFLOW/), (VNSPOJ FASTFLOW)[https://vn.spoj.com/problems/FFLOW/), and [a Chinese LOJ Flow Problem](https://loj.ac/problem/127) (it's intended to solve this problem with Highest Label Preflow Push, which has $O(V^2\sqrt{E})$ complexity).↵
↵
Also, to vouch for the superiority of my solution, here's some benchmarks with other implementations :^)↵
[Mine (to enable scaling change the SCALING boolean)](https://gist.github.com/Chillee/ad2110fc17af453fb6fc3357a78cfd28), [Emaxxs dinic](https://cp-algorithms.com/graph/dinic.html), [LOJ fastest (HLPP, the fastest submission on the Chinese flow problem)](https://loj.ac/submission/376520). As I was doing these benchmarks I realized the LOJ submission is actually faster than mine on all of my benchmarks :'(. It is substantially longer than my implementation though :^)↵
↵
SPOJ (V<=5000, E<=3e4) ↵
Mine: 0.04 ↵
Emaxx Dinic: 0.11 ↵
Mine w/ scaling: 0.27 ↵
LOJ fastest: 0.10 ↵
↵
↵
↵
VNSPOJ (V<=5000, E<=3e4, harder test cases): ↵
Mine: TLE ↵
Emaxx dinic: TLE ↵
Mine w/ scaling: 0.00 ↵
LOJ fastest: 0.00 ↵
↵
↵
↵
LOJ (V<=1200, E<=120000): ↵
Mine: 56 points ↵
Mine w/ scaling: 88 points ↵
Emaxx dinic: 44 points ↵
LOJ fastest: AC, 1176 ms total, #1 on leaderboard↵
↵
Synthetic Test(N=2000, E=4e6): ↵
Mine: 66.56 ↵
Emaxx dinic: 247.40 ↵
Mine w/ scaling: 0.14 ↵
LOJ fastest: 0.10 ↵
↵
#Number of non-whitespace characters:↵
Mine:7811164 ↵
Emaxx dinic:9181326 ↵
LOJ fastest:924 ↵
↵
↵
2228 ↵
↵
## Conclusions:↵
First off, HLPP seems to be superior to Dinic's in terms of runtime, at the cost of being approximately twice as long to implement. Also, I hope to provide a solid well-tested implementation of Dinic's with scaling that people can use. Other than that, however, I hope it's clear that Dinic's with scaling really does have a significant improvement in runtime (approximately a factor of V), and that translates to significantly better performance on real problems.↵
↵
PS: If anyone has a flow implementation they think is better than mine, I'd like to see it :^)↵
↵
↵
I had the same doubts. In fact, a couple months ago I benchmarked Dinic's with scaling on some hard [test cases](https://mirror.codeforces.com/blog/entry/52714?#comment-397861) and thought that Dinic's with/without scaling performed similarly.↵
↵
As it turns out, I benchmarked it again yesterday and found that Dinic's with scaling definitely has significantly better asymptotic complexity (by a factor of V). ↵
↵
## Synthetic Benchmarking↵
I used the hard test case generator at 2 posted by [user:ko_osaga,2019-03-18] [here](https://mirror.codeforces.com/blog/entry/52714?#comment-397861). The one posted at 1 creates a graph with only V edges and moreover, doesn't work for me... Notably, given a V, it generates a graph with V nodes and $O(V^2)$ edges.↵
↵
The code I used was my own Dinic's implementation (originally from emaxx) found [here](https://gist.github.com/Chillee/ad2110fc17af453fb6fc3357a78cfd28). Notably, the `SCALING` variable toggles between Dinic's with scaling and without. It's a small change, as you can see.↵
↵
I ran the two code across a variety of input sizes, averaging across 10 runs, then taking the log of input size and times, plotting them in a  where blue is the runtime of Dinic's without scaling and orange is the runtime of Dinic's with scaling. Since the important thing to look at is the slope of the line, I normalized the lines to start at the same point.↵
↵
Fitting a linear regression to the points, we see that the slope of Dinic's without scaling is 3.204, while the slope of Dinic's with scaling is 1.93, which correspond to complexities of $O(V^3)$ and $O(V^2)$ respectively. ↵
↵
In terms of actual runtime, here are some numbers on specific sizes.↵
↵
## Benchmarking on Problems↵
There are 3 flow problems, I benchmarked on — [SPOJ FASTFLOW](https://www.spoj.com/problems/FASTFLOW/), (VNSPOJ FASTFLOW)[https://vn.spoj.com/problems/FFLOW/), and [a Chinese LOJ Flow Problem](https://loj.ac/problem/127) (it's intended to solve this problem with Highest Label Preflow Push, which has $O(V^2\sqrt{E})$ complexity).↵
↵
Also, to vouch for the superiority of my solution, here's some benchmarks with other implementations :^)↵
[Mine (to enable scaling change the SCALING boolean)](https://gist.github.com/Chillee/ad2110fc17af453fb6fc3357a78cfd28), [Emaxxs dinic](https://cp-algorithms.com/graph/dinic.html), [LOJ fastest (HLPP, the fastest submission on the Chinese flow problem)](https://loj.ac/submission/376520). As I was doing these benchmarks I realized the LOJ submission is actually faster than mine on all of my benchmarks :'(. It is substantially longer than my implementation though :^)↵
↵
SPOJ (V<=5000, E<=3e4) ↵
Mine: 0.04 ↵
Emaxx Dinic: 0.11 ↵
Mine w/ scaling: 0.27 ↵
LOJ fastest: 0.10 ↵
↵
↵
Mine: TLE ↵
Emaxx dinic: TLE ↵
Mine w/ scaling: 0.00 ↵
LOJ fastest: 0.00 ↵
↵
↵
Mine: 56 points ↵
Mine w/ scaling: 88 points ↵
Emaxx dinic: 44 points ↵
LOJ fastest: AC, 1176 ms total, #1 on leaderboard↵
↵
Synthetic Test(N=2000, E=4e6): ↵
Mine: 66.56 ↵
Emaxx dinic: 247.40 ↵
Mine w/ scaling: 0.14 ↵
LOJ fastest: 0.10 ↵
↵
Mine:
Emaxx dinic:
LOJ fastest:
↵
↵
↵
## Conclusions:↵
First off, HLPP seems to be superior to Dinic's in terms of runtime, at the cost of being approximately twice as long to implement. Also, I hope to provide a solid well-tested implementation of Dinic's with scaling that people can use. Other than that, however, I hope it's clear that Dinic's with scaling really does have a significant improvement in runtime (approximately a factor of V), and that translates to significantly better performance on real problems.↵
↵
PS: If anyone has a flow implementation they think is better than mine, I'd like to see it :^)↵
↵
