#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const double EPS = 1e-9;
int N, M;
vector<int> adj[32], weight[32];
double solve(double* out) {
double A[32][32] = {0.0, }, B[32] = {0,0, };
for (int u = 0; u < N; ++u) {
A[u][u] = 1.0;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
int w = weight[u][i];
A[u][v] = -1.0/out[u];
B[u] += 1.0*w/out[u];
}
}
// Gauss Elimination
for (int i = 0; i < N; ++i) {
// Find Max Coefficient Row
double mx = 0.0;
int index = -1;
for (int j = i; j < N; ++j) {
if (abs(A[j][i] > mx)) {
mx = abs(A[j][i]);
index = j;
}
}
// Swapping
for (int j = 0; j < N; ++j)
swap(A[i][j], A[index][j]);
swap(B[i], B[index]);
// Target Variable's Coefficient to 1
double coefficent = A[i][i];
for (int j = 0; j < N; ++j)
A[i][j] /= coefficent;
B[i] /= coefficent;
// Remove A Variable and Recalculate Matrix
for (int j = 0; j < N; ++j) {
if (j != i && abs(A[j][i]) > EPS) {
double temp = A[j][i];
for (int k = 0; k < N; ++k)
A[j][k] -= temp * A[i][k];
B[j] -= temp * B[i];
}
}
}
return B[0];
}
int main() {
double out[32] = {0.0, };
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].push_back(v);
weight[u].push_back(w);
out[u]++;
}
printf("%.10lf\n", solve(out));
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
1672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
