Cod sursa(job #647651)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 11 decembrie 2011 18:19:03
Problema Flux maxim Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
using namespace std;
#include<fstream>
#include<vector>
int n,m;
vector <int> v[1010];
int c[1010][1010];
int t[1010],coada[1001000],viz[1010];
int BFS()
{int i,nr=2,nod,j,k,vec;
for(i=0;i<=n;viz[i]=0,i++);
viz[1]=1;
coada[1]=1;
for(i=1;i<nr;i++)
	{nod=coada[i];
	k=v[nod].size();
	for(j=0;j<k;j++)
		{vec=v[nod][j];
		if(viz[vec]==0&&c[nod][vec]>0)
			{viz[vec]=1;
			t[vec]=nod;
			coada[nr++]=vec;
			if(vec==n)
				return 1;
			}
		}
	}
return 0;
}
void citire()
{int x,y,e,i;
ifstream in("maxflow.in");
in>>n>>m;
for(i=0;i<m;i++)
	{in>>x>>y>>e;
	v[x].push_back(y);
	v[y].push_back(x);
	c[x][y]=e;
	}
in.close();
}
int main()
{int i,flow,mn,INF=1<<30;
citire();
for(flow=0;BFS();flow+=mn)
	{mn=INF;
	for(i=n;i>1;i=t[i])
		mn=min(mn,c[t[i]][i]);
	for(i=n;i>1;i=t[i])
		{c[i][t[i]]+=mn;
		c[t[i]][i]-=mn;
		}
	}
ofstream out("maxflow.out");
out<<flow<<'\n';
out.close();
return 0;
}