Cod sursa(job #726361)

Utilizator rares192Preda Rares Mihai rares192 Data 27 martie 2012 10:32:32
Problema Flux maxim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

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

#define INF 0x3f3f3f3f
#define NMAX 1025

int flux[NMAX][NMAX], cap[NMAX][NMAX];
int n, m, x, y, z;
int t[NMAX];

void Read();
bool BF(int, int);
int Flux();

int main()
{
	Read();
	fout << Flux() << '\n';
	fout.close();
	return 0;
}

void Read()
{
	fin >> n >> m;
	while( m )
	{
		fin >> x >> y >> z;
		cap[x][y] = z;
		--m;
	}
	fin.close();
}

bool BF(int s, int d)
{
	int Q[NMAX];
	memset(t, 0, sizeof(t));
	t[s] = -1;
	Q[0] = s;
	
	for(int p = 0, u = 0; p <= u; ++p)
		for(int i = 1, nod = Q[p]; i <= n; ++i)
			if( !t[i] && cap[nod][i] > flux[nod][i])
			{
				Q[++u] = i;
				t[i] = nod;
				if( i == d)
					return 1;
			}
	return 0;
}

int Flux()
{
	int flux_max = 0, r;
	while( BF(1, n) )
	{
		for(int i = 1; i <= n; ++i)
		{
			if(t[i] <= 0 || cap[i][n] <= flux[i][n])
				continue;
			
			r = cap[i][n] - flux[i][n];
			
			for(int j = i; j != 1; j = t[j])
				r = min(r, cap[ t[j] ][j] - flux[ t[j] ][j]);
			
			if( !r)
				continue;
			
			flux[i][n] += r;
			flux[n][i] -= r;
			
			for(int j = i; j != 1; j = t[j] )
			{
				flux[ t[j] ][j] += r;
				flux[j][ t[j] ] -= r;
			}
			flux_max += r;
		}
	}
	return flux_max;
}