:P

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 202 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2021 01:47:43 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

this is to allow flow to go back if our choice of path wasn't optimal, to see this lets check this case Lets assume we have a graph with 6 nodes and 7 edges (u v cap) (0 1 1) (0 2 1) (1 3 1) (1 4 1) (2 3 1) (3 5 1) (4 5 1) with s = 0,t = 5 if the first augmenting path we found is 0,1,3,5 and we increased flow along the edges of that path and didn't decrease flow in the opposite direction. in the second iteration we'll find no more augmenting paths. however if we decrease the flow in the opposite direction, this will allow an augmenting path 0,2,3,1,4,5 to be found and this makes the maximum flow 2.

so intuitively you may think of the decreasing flow in the reverse direction step as a way to undo any mistakes we made by taking the wrong augmenting path (the path which doesn't lead to maximum flow in the end).