Cod sursa(job #286403)

Utilizator oznmonkeyZene Andrei Cristian oznmonkey Data 23 martie 2009 19:49:09
Problema Flux maxim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream.h>
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?x:-x)

ifstream fin("flux.in");
ofstream fout("flux.out");

int c[1001][1001],f[1001][1001],s,d,viz[1001],n;

void citire();
void ek();
int bfs();
void afisare();

int main()
{
	citire();
	ek();
	afisare();
	return 0;
}

void citire()
{
	int x,y,z,m;
	fin>>n>>m;s=1;d=n;
	for(int i=1;i<=m;i++) {
		fin>>x>>y>>z;
		c[x][y]=z;
	}
}

void ek()
{
	int a,b, lg, v, l[1001],i;
	do {
		for(i=1;i<=n;i++) viz[i]=0;
		if(bfs()) return;
		a=b=10000;
		l[0]=d;lg=0;
		while(l[lg]!=s) {
			++lg;
			l[lg]=abs(viz[l[lg-1]]);
			if(viz[l[lg-1]]>0)
				a=min(a,c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]);
			else if(viz[l[lg-1]]<0)
				b=min(b,f[l[lg-1]][l[lg]]);
		}
		v=min(a,b);
		for(i=0;i<lg;i++) {
			if(viz[l[i]]>0)
				f[l[i+1]][l[i]]+=v;
			else if(viz[l[i]]<0)
				f[l[i]][l[i+1]]-=v;
		}
	}
	while(1);
}

int bfs()
{
	int p,u,q[1001],x,i;
	q[0]=s;p=u=0;viz[s]=1;
	while(p<=u && !viz[d]) {
		x=q[p++];
		for(i=1;i<=n;i++)
			if(!viz[i])
				if(f[x][i]<c[x][i]) {
					viz[i]=x;
					q[++u]=i;
				}
				else if(f[i][x]<c[i][x]) {
					viz[i]=-x;
					q[++u]=i;
				}
	}
	return !viz[d];
}
		
void afisare() 
{
	int i,vf=0;
	for(i=1;i<=n;i++)
		vf+=f[i][d];
	fout<<vf<<'\n';
}