Hello everyone!↵
↵
I have been trying to solve problem 1273 on POJ ([http://poj.org/problem?id=1273](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));↵
}↵
}↵
~~~~~↵
↵
↵
I have been trying to solve problem 1273 on POJ ([http://poj.org/problem?id=1273](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));↵
}↵
}↵
~~~~~↵
↵
