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

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

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
  • Проголосовать: не нравится

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

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I know that my rank is low, but I'm studying a lot about graph theory, I think flows would be a next path since I'm starting to deal good with searches, shortest-paths, bridges and cut points, but I'm also training in other topics as DP, geometry and greedy ;)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Many green and blue ranked users know flow.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

      Oh, certainly it helps them a lot while they try to solve something like Div2 B/C/D.
      Why are they learn all these flows, treaps, suffix arrays if they cannot solve problems which don't require any knowledge of algorithms?

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        hello, mr. dalex , learning algorithms is not just for contest or problem solving, its for life and fun. then does it matter whether one person is violet or orange ?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        dalex You took birth, started competitive programming and without learning algorithms you directly became orange huh?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes. I recently learned maxflow and the implementation of Dinic's algorithm. But I have a problem. I'm trying to solve FASTFLOW in SPOJ and I'm getting TLE with Dinic's algorithm. How to optimize? Here is my implementation — http://codeforces.net/blog/entry/15562

»
12 лет назад, # |
  Проголосовать: нравится 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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you, I'm pretty sure it's correct also, do you know any problem which asks for maximum flow without a too strict time as FASTFLOW ? but I think it's wrong also, since there's a possible flow of 3 in the path 1 — 2 — 3 — 4 and 2 from 1 — 3 — 4.

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

      Oh, i got it: these are undirected edges. So for every edge (u, v, c), you should put also edge (v, u, c).

      Maybe you can find some problems on maxflow here on Codeforces, try searching the problems from the archive on maxflow tag or smth. Also I recall, Dinic's algorithm gets accepted on FASTFLOW.

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

        but I'm mounting as an undirected graph, take a look:

        memset(capacity, 0, sizeof(capacity));
            int n, m, a, b, c;
            scanf("%d%d", &n, &m);
            for(int i = 0; i < m; i++) {
                scanf("%d%d%d", &a, &b, &c);
                graph[a].push_back(b); capacity[a][b] = c;
                graph[b].push_back(a); capacity[b][a] = c;
            }
        
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

          That's because there are edges (3, 4, 3) and (4, 3, 3) in input. The code overwrites the previous capacities. Add them up and it'll be cool.

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

            Yes, it was the problem, thank you, I'll look for more flow problems, ;) Thanks.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have solved these problems in java, time limit is not strict.

      Data Flow

      Internet Bandwidth

      The Problem with the Problem Setter

      Sabotage

»
10 лет назад, # |
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].

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    After reading your comment, I still don't see why the implementation is wrong. The array residual is there to avoid unnecessary changes to array capacity, which can be used somewhere later in the code.

    Aren't capacity[u][v] -= actual[sink] and residual[u][v] += actual[sink] the same?

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      You are right, I think only taking the graph[] as undirected one will do. Sorry for the confusion.

»
10 лет назад, # |
  Проголосовать: нравится 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.