UVA -Internet Bandwidth getting wrong answer

Revision en1, by pvpcoder, 2015-09-14 19:33:28

I am trying [this problem].The problem is about finding the max-flow in the graph.
I used Edmond-karp algorithm to solve this but I am getting wrong answer.It would be helpful if any one spotify the error.(https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=761)

#include<bits/stdc++.h>
using namespace std;
#define MX 1000000007
#define LL long long
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define len(x) x.length()
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define FORE(i,a,n) for(int i=a;i<=n;i++)
template<class T1> inline T1 maxi(T1 a,T1 b){return a>b?a:b;}
template<class T2> inline T2 mini(T2 a,T2 b){return a<b?a:b;}
int parent[101],G[101][101],rG[101][101];
bool bfs(int s,int t,int n)
{	
	bool vis[n+2];
	memset(parent,0,sizeof parent);
	memset(vis,0,sizeof vis);
	queue<int>Q;
	Q.push(s);
	vis[s]=true;
	while(!Q.empty())
	{
		int fnt=Q.front();
		Q.pop();
		for(int v=1;v<=n;v++)
		{
			if(!vis[v] and G[fnt][v]>0)
			{
				vis[v]=true;
				parent[v]=fnt;
				Q.push(v);
			}
		}
	}
	return vis[t];
}
int main()
{
	int n,tst=1;
	ri(n);
	while(n)
	{
		int s,t,c,flow=0;
		ri(s),ri(t),ri(c);
		FORE(i,1,c)
		{
			int x,y,z;
			ri(x),ri(y),ri(z);
			G[x][y]+=z;
			G[y][x]+=z;
		}
		while(bfs(s,t,n))
		{
			int path=9999999;
			for(int v=t;v!=s;v=parent[v])
			{
				int u=parent[v];
				path=mini(path,G[u][v]);
			}
			for(int v=t;v!=s;v=parent[v])
			{
				int u=parent[v];
				G[u][v]-=path;
				G[v][u]+=path;
			}
			flow+=path;
		}		
		printf("Network %d\nThe bandwidth is %d.\n\n", tst++, flow);
		ri(n);
	}
}

Tags flows, max-flow min-cut, graphs, algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pvpcoder 2015-09-14 19:34:39 204
en1 English pvpcoder 2015-09-14 19:33:28 1735 Initial revision (published)