Warriors_Cats's blog

By Warriors_Cats, history, 4 years ago, In English

Hello, everyone! Can someone explain me how to merely implement Dinic's algorithm for maximum flow using the linear logarithmic behaviour provided by dynamic trees such as link/cut trees described by Tarjan and Sleator. Despite the fact that I have seeked for the so called O(VElogV) version of Dinic's algorithm, however I didn't manage to find any appropriate implementation for it. Here are some suggestive articles I have recently found: https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.cc.gatech.edu/~rpeng/18434_S15/blockingFlows.pdf&ved=2ahUKEwiDi676jK_rAhUPxosKHX3YAyMQFjABegQIARAB&usg=AOvVaw3AI1kk_L7dXi9oF8yheGsd and https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.arl.wustl.edu/~jst/cse/542/text/sec19.pdf&ved=2ahUKEwiFobDfia_rAhVN_CoKHYIrC-YQFjAAegQIAhAB&usg=AOvVaw30d3vyyxayE8XX1bZsEFZq. Thanks a lot in advance for any suggestion or link!

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By Warriors_Cats, history, 4 years ago, In English

Hello, guys! Can anyone suggest me an appropiate idea on this shortest path task: https://cses.fi/problemset/task/1203/? I have already exhausted all my efficient approaches on this topic. Any eligible answer would be appreciated! Thanks a lot!

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it