sumit.chaturvedi's blog

Edmond Karp's Algorithm
By sumit.chaturvedi, history, 9 years ago, In English

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));
    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sumit.chaturvedi (previous revision, new revision, compare).

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I think that your problem could be the overflow. You use int as the output, but the capacities are between 0 and 10,000,000.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    This does not seem to be the reason. The maximum number of ditches given in the problem statement is N = 200. Therefore, the maximum flow of the drainage network when all these ditches are built in parallel between the pond and the stream cannot exceed 2,000,000,000. This upper bound can be represented using a 32-bit signed integer.

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      Ok, the reason then is the multiarcs, I'm now in the phone trying to help. :D

      → Reply
      • »
        »
        »
        »
        9 years ago, hide # ^ |
        ← Rev. 35  
        Vote: I like it +1 Vote: I do not like it

        This is a good guess. The problem statement does not indicate that at most one ditch is built between any pair of distinct intersection points. If this is the problem, then fixing it should be simple. Add the new capacity of the ditch to the existing capacity if it extends between the same source and same destination of an existing ditch instead of creating a new ditch.

        I have just tried the test case:

        5 4

        1 4 100

        1 4 100

        1 4 100

        1 4 100

        1 4 100

        And the output result from the code listed above is 100. The correct answer should be 500, as the total capacity between the pond and the stream is 500 because of the presence of 5 arcs each with capacity 100 between the pond and the stream as suggested. Replacing the statement:

         gf[u][w] = c;

        with

         gf[u][w] = c + ( gf[u][w] == INF ? 0 : gf[u][w] );

        produced the expected result for this test case of maximum flow 500. However, the #define constant INF should be replaced with INT_MAX so as to avoid conflict with some multiple-arcs test case whose total capacity of some ditch is equal to the present value of INF.

        Finally, it should be noted that the listed code does not consider the case when two ditches with given maximum capacities exist in the opposite directions between the same pair of intersection points. Check the first example in the following page for the two arcs between nodes 1 and 2.

        https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          First of all, thanks a ton for your inputs. However, the problem statement says "For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle. " I thought that this would rule out the possibility of multi arcs and also edges in opposite directions. Anyway I made these changes but still I didn't manage to pass :) ;(.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, hide # ^ |
            ← Rev. 3  
            Vote: I like it 0 Vote: I do not like it

            With pleasure. The other statement for updating the ditch capacity in the opposite direction

             gf[w][u] = 0;

            should be replaced with

             gf[w][u] = ( gf[w][u] == INF ? 0 : gf[w][u] );

            or

              if ( gf[w][u] == INF )
     gf[w][u] = 0;

            so as to leave the forward ditch capacity between u and w unchanged if a reverse ditch is declared.

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Your code was accepted at POJ after modifying the ditch capacity in the opposite direction and replacing INF with INT_MAX.

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, hide # ^ |
            ← Rev. 4  
            Vote: I like it 0 Vote: I do not like it

            The following is an update for your code that may be more readable. Note that the STL array fill() function has been implemented as the C++ compiler at POJ does not recognize the statement #include <array>. 

            #include <vector>
#include <bitset>
#include <iostream>
#include <queue>

using namespace std;

class flow_graph_t
{
    static const int V = 200, E = 200;

    template< class T, size_t Size >
    struct array: vector< T >
    {
        array()
        {
            vector< T >::resize( Size );
        }

        void fill( const T &value )
        {
            for( size_t i = 0; i < Size; i++ )
                vector< T >::at( i ) = value;
        }
    };

    typedef array< int, V > array_t;

    array< array_t, V > C;

    void read_edge()
    {
        int Si, Ei, Ci; cin >> Si >> Ei >> Ci;

        if ( C[ --Si ][ --Ei ] == INT_MIN )
            C[ Si ][ Ei ]  = Ci;
        else
            C[ Si ][ Ei ] += Ci;

        if ( C[ Ei ][ Si ] == INT_MIN )
            C[ Ei ][ Si ] = 0;
    };

    struct queue_t: queue< int >
    {
        bitset< V > marked;

        void mark( const int i )
        {
            push( i ), marked.set( i );
        }

        int next()
        {
            int i = front(); pop(); return i;
        }
    };

    array_t path; int T;

    bool path_exists( const int N )
    {
        queue_t q;

        for( path.fill( -1 ), q.mark( 0 ); !q.empty(); )
            for( int i = q.next(), j = 0; j < N; j++ )
                if( C[ i ][ j ] > 0 && !q.marked[ j ] )
                {
                    path[ j ] = i, q.mark( j );

                    if( j == T )
                        return true;
                }

        return false;
    }

    int max_flow()
    {
        int j = T, i = path[ j ], k = INT_MAX;

        while( i != -1 )
            k = min( k, C[ i ][ j ] ), i = path[ j = i ];

        for( i = path[ j = T ]; i != -1; i = path[ j = i ] )
            C[ i ][ j ] -= k,
            C[ j ][ i ] += k;

        return k;
    }

public:

    flow_graph_t( const int M, const int N ) : T( N - 1 )
    {
        for( int i = 0; i < N; i++ )
            C[ i ].fill( INT_MIN );

        for( int i = 0; i < M; i++ )
            read_edge();
    }

    int max_flow( const int N )
    {
        int flow = 0;

        while( path_exists( N ) )
            flow += max_flow();

        return flow;
    }
};

int main()
{
    ios_base::sync_with_stdio( false ), cin.tie( 0 ), cout.tie( 0 );

    for( int M, N, P; cin >> M >> N; cout << P << '\n' )
    {
        flow_graph_t flow_graph( M, N );

        P = flow_graph.max_flow( N );
    }
}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              Great! Yes you are right, I was able to pass the test cases on POJ. Finally! I'm grateful to you for your help. I had written a code which is similar to yours using scaling max flow algorithm (Consider paths with capacity at least delta first and if non found, decrease delta by half and continue until delta = 1). That was written in modular fashion. I suspect even that had the same problem which is why it wasn't getting accepted. Anyway, given how they framed the question, I didn't think that such test cases would be provided. Again thanks for your help and best of luck!

              → Reply