求从1开始，在一个有向图中经过某条边次数的期望。
E[p]=sigma(E[t]/deg[t])，t为能到p的点的集合，deg[t]为t的度数。对于起点要额外加1，因为第一次肯定会被运行一次。
高斯消元看的Rujia的代码，注意对无解的判断。
1 #include <string.h> 2 #include <stdio.h> 3 #include <vector> 4 #include <math.h> 5 #define MAXN 105 6 using namespace std; 7 const double eps = 1e-9; 8 int n, q, deg[MAXN]; 9 int tu, tv; 10 vector<int> e[MAXN]; 11 double x[MAXN][MAXN]; 12 int inf[MAXN]; 13 void gauss(int n){ 14 for (int r = 1; r <= n; r++) { 15 int maxr = r; 16 for (int i = r+1; i <= n; i++) 17 if (fabs(x[i][r] > fabs(x[maxr][r]))) maxr = r; 18 if (fabs(x[maxr][r]) < eps) continue; 19 if (maxr != r) 20 for (int i = 1; i <= n+1; i++) swap(x[maxr][i], x[r][i]); 21 for (int i = 1; i <= n; i++) if (i != r){ 22 for (int j = n+1; j >= r; j--) 23 x[i][j] -= x[i][r]/x[r][r]*x[r][j]; 24 } 25 } 26 memset(inf, 0, sizeof inf); 27 for (int i = n; i >= 1; i--) { 28 if (fabs(x[i][n+1])>eps && fabs(x[i][i])<eps) inf[i] = 1; 29 else if (fabs(x[i][n+1])<eps) x[i][i] = 0; 30 else x[i][i] = x[i][n+1]/x[i][i]; 31 for (int j = i+1; j <= n; j++) { 32 if(fabs(x[i][j])>eps && inf[j]) inf[i] = 1; 33 } 34 } 35 } 36 int main(){ 37 //freopen("test.in","r",stdin); 38 int cas = 1; 39 while (scanf("%d", &n), n) { 40 memset(deg, 0, sizeof deg); 41 for (int i = 1; i <= n; i++) e[i].clear(); 42 while (scanf("%d%d", &tu, &tv), tu||tv) { 43 deg[tu]++; 44 e[tv].push_back(tu); 45 } 46 memset(x, 0, sizeof x); 47 x[1][n+1] = 1.0; 48 for (int i = 1; i <= n; i++) { 49 x[i][i] = 1.0; 50 for (int j = 0; j < e[i].size(); j++) 51 x[i][e[i][j]] -= 1.0/deg[e[i][j]]; 52 } 53 gauss(n); 54 printf("Case #%d:\n", cas++); 55 scanf("%d", &q); 56 while (q--) { 57 scanf("%d", &tu); 58 if (inf[tu]) printf("infinity\n"); 59 else printf("%.3f\n", x[tu][tu]); 60 } 61 } 62 return 0; 63 }