Cod sursa(job #423018)

Utilizator FlorianFlorian Marcu Florian Data 23 martie 2010 13:56:30
Problema Flux maxim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
using namespace std;
#include<fstream>
#include<vector>
#include<iomanip>
#include<cmath>
#include<queue>
#define pb push_back
const int MAX_N = 207;
const double oo = 0x3f3f3f3f;
double capac[MAX_N][MAX_N];
vector<int>G[MAX_N];
int tata[MAX_N], d[MAX_N], N, M;
int BFS()
{
	queue<int>Q;
	int i, x, y;
	Q.push(1);
	for(i = 1; i <= N; ++i) d[i] = 0;
	d[1]  = 1;
	for(;!Q.empty();Q.pop())
	{
		x = Q.front();
		for(i = 0; i < G[x].size(); ++i)
		{
			y = G[x][i];
			if(capac[x][y] != 0 && !d[y] )
			{
				d[y] = 1;
				tata[y] = x;
				Q.push(y);
			}
		}
	}
	return d[N];
}
double SOL;
int main()
{
	ifstream in("fear.in"); ofstream out("fear.out");
	in>>N>>M;
	int a, b, i; double c;
	for(i = 1; i <= N; ++i)
	{
		in>>a>>b>>c;
		G[a].pb(b);
		G[b].pb(a);
		capac[a][b] = log(c);
		capac[b][a] = log(c);
	}
	double f;
	for(; BFS();)
	{
		f = oo;
		for(i = N; i!=1; i=tata[i])
			f = min(f, capac[tata[i]][i]);
		for(i = N; i!=1; i=tata[i])
		{
			capac[tata[i]][i] -= f;
			capac[i][tata[i]] += f;
		}
		SOL += f;
	}
	SOL = exp(SOL);
	out<<setprecision(4)<<fixed<<SOL<<"\n";
	return 0;
}