Edmond Karp's Algorithm

Revision en2, by sumit.chaturvedi, 2018-03-31 20:20:58

Hello everyone!

I have been trying to solve problem 1273 on POJ (http://poj.org/problem?id=1273). According to me, it is a straight forward application of a max-flow algorithm. But there is some problem in my implementation. I have searched online for the solution and generated test cases. Both the online solution and mine pass them. Yet POJ doesn't accept my solution. I have gone through my code atleast 10 times. If someone can point out my mistake, I'll be really grateful.

Your code here...
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>

#define fori(i,n) for(int i = 0; i < n; i++)
#define INF 10000005

using namespace std;
// Stores the residual graph
vector<vector<long long> > gf;

void reset_graph(int v){
    fori(i,v){
        fori(j,v){
            gf[i][j] = INF;
        }
    } 
}

int ekarp(int v){
    bool path_exists = true;
    int flow = 0;
    while(path_exists){
        path_exists = false;
        vector<int> path(v,-1);
        vector<bool> marked(v, false);
        queue<int> q;
        q.push(0);
        marked[0] = true;
        while(!q.empty() && !path_exists){
            int tp = q.front();
            q.pop();
            fori(i,v){
                if(gf[tp][i] < INF && !marked[i] && gf[tp][i] > 0){
                    q.push(i);
                    marked[i] = true;
                    path[i] = tp;
                    if(i == v-1){
                        path_exists = true;
                    }
                }
            }
        }
        if(path_exists){
            long long bn = INF;
            int prev = v-1;
            while(path[prev] != -1){
                bn = min(bn,gf[path[prev]][prev]);
                prev = path[prev];
            }
            prev = v-1;
            while(path[prev] != -1){
                gf[path[prev]][prev] -= bn;
                gf[prev][path[prev]] += bn; 
                prev = path[prev];
            }
            flow+= bn;
        }
    }
    return flow;
}

int main(){
    int e,v;
    gf.resize(205);
    fori(i,205) gf[i].resize(205,INF);
    while(scanf("%d%d", &e, &v) != EOF){
        reset_graph(v);
        fori(i, e){
            int u,w,c;
            scanf("%d%d%d", &u, &w, &c);
            u--;
            w--;
            gf[u][w] = c;
            gf[w][u] = 0;
        }
        printf("%d\n", ekarp(v));
    }
}
Tags #network flow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sumit.chaturvedi 2018-03-31 20:20:58 39 Tiny change: 'n\n~~~~~\n\n~~~~~\n\' -> 'n\n~~~~~\nYour code here...\n~~~~~\n\'
en1 English sumit.chaturvedi 2018-03-31 20:18:21 2510 Initial revision (published)