Блог пользователя aajjbb

Автор aajjbb, 14 лет назад, По-английски

Hi, I'm really new to Flow algorithms and I'm starting with maximum flow using the EdmondsKarp, I've implemented this version, for the test example extracted from SPOJ FASTFLOW the following test-case has a max-flow of 5, my code answers 3. what would be wrong ? Thanks

Test-Case:

4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3
int max_flow(int source, int sink) {
    int residual[MAXN][MAXN]; memset(residual, 0, sizeof(residual));
    while(1) {
        int prev[MAXN]; memset(prev, -1, sizeof(prev));
        int actual[MAXN]; memset(actual, 0, sizeof(actual));
        prev[source] = source;
        actual[source] = INF;
        queue<int> q; q.push(source);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i];
                if(capacity[u][v] - residual[u][v] > 0 && prev[v] == -1) {
                    prev[v] = u;
                    actual[v] = min(actual[u], capacity[u][v] - residual[u][v]);
                    if(v != sink) {
                        q.push(v);
                    } else {
                        while(prev[v] != v) {
                            u = prev[v];
                            residual[u][v] += actual[sink];
                            residual[v][u] -= actual[sink];
                            v = u;
                        }
                        goto end;
                    }
                }
            }
        }
        end:;
        if(prev[sink] == -1) {
            int sum = 0;
            for(int i = 0; i < MAXN; i++) {
                sum += residual[source][i];
            }
            return sum;
        }
    }
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Better forget about maximum flow unless your handle becomes violet or orange.

»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think your code is correct, the max flow value here is 3. The edge (3, 4) can handle only flow of 3, not 5.

By the way you code is very pretty. (:

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Your implementation is incorrect.

Taking the line "int maxflow(.." as line 1, in lines 21 and 22, you should be updating the capacity matrix as capacity[u][v] -= actual[sink], capacity[v][u] += actual[sink], also increase residual flow as residual[u][v] += actual[sink]. For finding augmenting path in the residual graph, you will need to check if there exists an edge between u and v in the residual graph. That is, in line 11, you will need to check all vertices that can take a flow from u at any point of time. Therefore it is better to take the graph[] as undirected one, or check for all vertices if capacity[u][v] > 0. Similarly in line 15, actual[v] will be checked for minimum with capacity[u][v] and not capacity[u][v] — residual[u][v].

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I don't know how Edmonds Karp works , but i know Dinic algorithm and i know that dinic is better that edmonds karp if we are talking about complexities.

Wiki

Nice Implementation of FASTFLOW with Dinic

Maybe this be can help you.