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));
}
}



