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. ~~~~~

include

include

include

include

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

define INF 10000005

using namespace std; // Stores the residual graph vector<vector > 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 path(v,-1); vector marked(v, false); queue 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)); } } ~~~~~