Question in Dinic

Правка en1, от purple_dreams, 2017-08-08 22:32:23

In Dinic algorithm for maximum flow, we in dfs we write the function as

for(int &t = ptr[source]; t < neighbours of source ; ++t)

I read that ptr is an array used to make finding the blocking flow in O(m) rather than O(m2). Why does this work and what is the exact use of keeping the ptr array. How does this array work?

Теги maxflow, dinic

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский purple_dreams 2017-08-08 22:32:23 361 Initial revision (published)