时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
Special Judge, 64bit IO Format: %lld
题目描述
先考虑下面这个原始问题：
给定一个由 N 个点及 M 条有正整数权重的有向边组成的图。点的编号由 0 至 N-1。
此图中可以有自环 (自己指向自己的边)，但是对于任何的有序点对 (a, b)，由 a 至 b 的边最多只会有一条。
在这张图中，有一个旅人，他会按照下列的规则进行移动：如果他所在的点没有任何向外的边，那他就不会移动。如果有恰好一条的对外边，那他就会走到那条对外边所指向的点。如果有超过一条的对外边，那他将会随机选择一条进行移动，每条对外边被选中的概率正比于它的权重。
我们不知道这个旅人现在在哪里，但是我们知道这个旅人现在在这张图中每个点的概率，请问，这个旅人走一步之后，他在这张图中每个点的概率各是多少呢？
蜥蜴觉得这题超级简单，于是很快地写完了一个正确的解答，并且输入原题的样例测试，但是没想到，蜥蜴的程式的输出竟然跟输入一样！也就是说，这个旅人给定的概率分布，跟他走一步之后的概率分布竟然完全一致！蜥蜴觉得这样的测试数据真的太酷了，他也想要产生这样的测试数据，于是，他决定把这个问题交给各位参赛者：对于给定的一张图，请找出一组原题的测试数据，使得原题的答案跟测试数据一致！
输入描述:
输入的第一行有两个正整数N, M，分别代表原题中的图的点数及边数。
接下来的M行每行有三个整数a, b, w，分别代表一条a至b的有向边，其权重为w。
输出描述:
如果没有这种测试数据存在，请在一行中输出Impossible。否则，请输出N行，第i行中有一个浮点数，代表旅人一开始在点i - 1的概率。如果有超过一种可能的答案，输出任意一种皆可。此题的评审方式如下：如果答案为Impossible，则必须输出Impossible才正确。而在有可能答案的测试数据，则不能输出Impossible。浮点数输出的部分，读入后的总和必须和1之间的误差(相对或绝对)不超过10-9，否则评判为错误。按照蜥蜴原题的代码执行，求得旅人下一步的概率分布，如果对于每个点，下一步的概率跟读入的概率误差(相对或绝对)不超过10-9，则评判为正确，否则为错误。
示例1
输入
3 3
0 1 1
1 2 1
2 0 1
输出
0.33333333333333331483
0.33333333333333337034
0.33333333333333331483
示例2
输入
2 4
0 1 4
0 0 6
1 0 7
1 1 3
输出
0.63636363636363635354
0.36363636363636364646
备注:
1≤N≤100
0≤M≤10000
0≤a,b<N
1≤w≤10
任何的有序点对 (a, b)，由 a 至 b 的边最多只会有一条
题目链接：D.图图
题意就是给你一个$n$个点图中点与点之间的权重矩阵，然后再告诉你在每一个点的概率和它走一步即转移一次的概率是相同的，燃鹅比赛的时候没想出来。
其实这题跟挑战程序设计竞赛那本书上的求期望的题是差不多的，假设在一个点的概率为$P_i$，然后题目中说从$u \to v$转移的概率是
然后考虑每一个点$i$都具有形如这样的等式：
如果一个点$j$没有连出去的边，那么就加一条它自己连向自己的边，权值随便取一个方便的数就行，反正除一下概率还是$1$。
当然还要加上最重要的一条:$\sum_1^n P_i=1$
那么将这个方程组变成一个
$(n+1)*(n+1)$的增广矩阵，高斯消元一下就可以了，这题感觉有点卡精度，交了20多发用了别人的高斯消元模板再把保留的小数从$20$位改到$14$位才过，贼奇怪……
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
const int N = 105;
const double eps = 1e-11;
double sw[N];
double A[N][N];
vector<pair<int, double> >in[N];
int Gaussian(int n)
{
register int ce, i, j, te;
for (ce = 1; ce <= n + 1; ++ce)
{
te = ce;
for (i = ce + 1; i <= n + 1; ++i)
if (fabs(A[i][ce]) > fabs(A[te][ce]))
te = i;
if (fabs(A[te][ce]) < eps)
continue;
if (te != ce)
for (j = 1; j <= n + 1; ++j)
swap(A[ce][j], A[te][j]);
for (i = 1; i <= n + 1; ++i)
{
if (i != ce)
for (j = n + 1; j >= ce; --j)
A[i][j] -= A[i][ce] * A[ce][j] / A[ce][ce];
}
}
for (i = 1; i <= n; ++i)
if (fabs(A[i][i]) < eps && fabs(A[i][n + 1]) > eps)
return 0;
return !(A[n + 1][n + 1] > eps);
}
int main(void)
{
register int n, m, i, a, b;
register double w;
scanf("%d%d", &n, &m);
for (i = 0; i < m; ++i)
{
scanf("%d%d%lf", &a, &b, &w);
++a, ++b;
in[b].push_back({a, w});
sw[a] += w;
}
for (i = 1; i <= n; ++i)
if (sw[i] == 0)
sw[i] = 1.0, in[i].push_back({i, 1.0});
for (i = 1; i <= n; ++i)
{
A[i][i] = 1.0;
for (auto &e : in[i])
{
A[i][e.first] -= e.second / sw[e.first];
}
}
for (i = 1; i <= n + 1; ++i)
A[n + 1][i] = 1.0;
if (!Gaussian(n))
puts("Impossible");
else
{
for (i = 1; i <= n; ++i)
{
if (fabs(A[i][i]) < eps)
printf("%.14f\n", 0.0);
else
printf("%.14f\n", A[i][n + 1] / A[i][i]);
}
}
return 0;
}