JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial Pseudocode
 Pseudocode | Reply I'm finally getting around to reading this article (and am enjoying it).However the formatting of the pseudocode is a little hard to read. Is there a separate "code source" that we can refer to that directly matches the pseudocode in the article?Also, what does "semnification" mean? Yahoo and Google can't define it, (in fact the #1 reference on Google is the Max-Flow article!)
 Re: Pseudocode (response to post by dplass) | Reply semnificatie (rom) == meaning (eng) :)
 Re: Pseudocode (response to post by dplass) | Reply that's funny! it is "significance" there...
 Re: Pseudocode (response to post by dplass) | Reply It looks that the pseudocode idea was not so good after all.I'll post some C++ code:```int bfs(int source) { bool visited[NMax]; memset(visited, false, sizeof(visited)); visited[source] = true; int from[NMax]; memset(from, -1, sizeof(from)); deque Q; Q.push_back(source);   while (!Q.empty()) { int where = Q.front(); Q.pop_front(); bool found = false; // lst[where] = the adjacency list of vertex where for (int i = 0; i < lst[where].size(); ++ i) { int next = lst[where][i]; if (!visited[next] && capacity[where][next] > 0) { Q.push_back(next); visited[next] = true; from[next] = where; if (next == sink) { found = true; break; } } } if (found) break; }   int where = sink, nflow = INFINITY; while (from[where] > -1) { int prev = from[where]; nflow = min(nflow, capacity[prev][where]); where = prev; } where = sink; while (from[where] > -1) { int prev = from[where]; capacity[prev][where] -= nflow; capacity[where][prev] += nflow; where = prev; } return nflow == INFINITY ? 0 : nflow; } ``````struct node { int at, cost; node(int at1, int cost1): at(at1), cost(cost1) {}; }; bool operator < (node a, node b) { return a.cost > b.cost; }   int pfs(int source) { int from[NMax]; memset(from, -1, sizeof(from)); int bst[NMax]; memset(bst, 0, sizeof(bst)); bst[source] = INFINITY; priority_queue pq; pq.push(node(source, INFINITY));   while (!pq.empty()) { int where = pq.top().at, cst = pq.top().cost; pq.pop(); if (bst[where] < cst) continue; if (where == sink) break; for (int i = 0; i < lst[where].size(); ++ i) { int next = lst[where][i]; int ncost = min(cst, capacity[where][next]); if (bst[next] < ncost) { bst[next] = ncost; pq.push(node(next, ncost)); from[next] = where; } } }   int where = sink; while (from[where] > -1) { int prev = from[where]; capacity[prev][where] -= bst[sink]; capacity[where][prev] += bst[sink]; where = prev; } return bst[sink]; } ```
 Re: Pseudocode (response to post by _efer_) | Reply Thanks.
 Re: Pseudocode (response to post by dplass) | Reply if we change ``` bool operator < (node a, node b) { return a.cost > b.cost; } to bool operator < (node a, node b) { return a.cost < b.cost; // > changed to < } ``` it dosen't work faster ?because we prefer maximum costs than minimum of that let me know if I`m wrong !
 Re: Pseudocode (response to post by beginner1010) | Reply By default priority queue stores maximal value in the top, but we need minimal value. To deal with it one can change operator < in such way that it works as usual operator >.
 Re: Pseudocode (response to post by K.A.D.R) | Reply I believe if we get maximal bottleneck in each iteration , it works faster
 Forums Tutorial Discussions Maximum Flow tutorial Pseudocode Previous Thread  |  Next Thread