Pagini recente » Cod sursa (job #63770) | Cod sursa (job #1253648) | Cod sursa (job #1579757) | Cod sursa (job #1919841) | Cod sursa (job #832035)
Cod sursa(job #832035)
#include <fstream>
#include <iomanip>
#include <vector>
#include <utility>
#define eps 0.000001
using namespace std;
vector<pair<int,int> >v[300];
int n, k, m, i, j, l, c, x, y, sum, vec;
double a[300][300], sol;
int main()
{
ifstream fi("tunel.in");
ofstream fo("tunel.out");
fi >> n >> m;
for(i = 1; i <= m; i++)
{
fi >> x >> y >> c;
v[x].push_back(make_pair(y,c));
v[y].push_back(make_pair(x,c));
}
for(i = 1; i <= n; i++)
{
vec = v[i].size();
if(i == 1) vec++;
sum = 0;
for(j = 0; j < v[i].size(); j++)
{
if(v[i][j].first == n)
{
vec--;
continue;
}
a[i][v[i][j].first] += -1;
sum += v[i][j].second;
}
a[i][i] = vec;
a[i][n+1] = sum;
}
i = 1; j = 1;
m = n;
while(i <= n and j <= m)
{
for(k = i; k <= n; k++)
if(a[k][j] < -eps or a[k][j] > eps) break;
if(k == n+1)
{
j++;
continue;
}
if(k != i)
for(l = 1; l <= m+1; l++) swap(a[i][l], a[k][l]);
for(l = j+1; l <= m+1; l++)
a[i][l] = (double)a[i][l]/a[i][j];
a[i][j] = 1;
for(l = i+1; l <= n; l++)
{
for(c = j+1; c <= m+1; c++)
a[l][c] -= (double)a[i][c]*a[l][j];
a[l][j] = 0;
}
i++; j++;
}
double x[300];
for(i = n; i > 0; i--)
for(j = 1; j <= m+1; j++)
if(a[i][j] < -eps or a[i][j] > eps)
{
if(j == m+1)
{
fo << "Imposibil\n";
return 0;
}
x[j] = a[i][m+1];
for(k = j+1; k <= m; k++) x[j] -= (double)x[k]*a[i][k];
break;
}
fo << setprecision(9) << fixed;
fo << x[n] << "\n";
return 0;
}