Pagini recente » Cod sursa (job #605325) | Cod sursa (job #1241784) | Cod sursa (job #2853572) | Cod sursa (job #3290299) | Cod sursa (job #2850725)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
#pragma GCC optimize ("Ofast")
ifstream fin("tunel.in");
ofstream fout("tunel.out");
struct nodul {
int nod, cost;
};
const double eps = 0.0001;
int n, m;
double mat[260][260], sol[260];
vector <nodul> G[260];
void schimb(int a, int b)
{
for(int i = 1; i <= n; i++)
swap(mat[a][i], mat[b][i]);
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y, c;
fin >> x >> y >> c;
G[x].push_back({y, c});
G[y].push_back({x, c});
}
for(int nod = 1; nod < n; nod++)
{
int nr_vec = G[nod].size(), total = 0;
for(nodul vecin : G[nod])
{
total += vecin.cost;
if(vecin.nod != n)
mat[nod][vecin.nod] += (double) 1 / nr_vec;
}
mat[nod][nod] = -1;
mat[nod][n] = - (double) total / nr_vec;
}
n--, m = n;
int i = 1, j = 1;
while(i <= n && j <= m)
{
int k;
for(k = i; k <= n; k++)
if(mat[k][j] < -eps || mat[k][j] > eps)
break;
if(k == n + 1)
{
j++;
continue;
}
if(k != i)
schimb(k, i);
for(k = j + 1; k <= m + 1; k++)
mat[i][k] = mat[i][k] / mat[i][j];
mat[i][j] = 1;
for(k = i + 1; k <= n; k++)
{
for(int l = j + 1; l <= m + 1; l++)
mat[k][l] -= mat[k][j] * mat[i][l];
mat[k][j] = 0;
}
i++, j++;
}
for(i = n; i > 0; i--)
{
for(int j = 1; j <= m + 1; j++)
{
if(mat[i][j] > eps || mat[i][j] < -eps)
{
if(j == m + 1)
{
fout << "Imposibil";
return 0;
}
sol[j] = mat[i][m + 1];
for(int k = j + 1; k <= m; k++)
sol[j] -= sol[k] * mat[i][k];
break;
}
}
}
fout << fixed << setprecision(3) << sol[1] << '\n';
return 0;
}