Pagini recente » Cod sursa (job #114653) | Cod sursa (job #1959139) | Borderou de evaluare (job #2591567) | Cod sursa (job #1250711) | Cod sursa (job #423018)
Cod sursa(job #423018)
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;
}