高斯消元求概率
对于非起点，期望x[i] = ∑x[j] / deg[j]
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 108, INF = 0x3F3F3F3F;
const double eps = 1e-8;
double f[N][N];
std::vector<int> g[N];
bool inf[N]; template<typename T>
void gauss(T A[N][N], int n){
for(int i = 0; i < n; i++){
int r = i;
for(int j = i + 1; j < n; j++){
if(abs(A[j][i]) > abs(A[r][i])){
r = j;
}
}
if(abs(A[r][i]) < eps){
continue;
}
if(r != i){
for(int j = 0; j <= n; j++){
swap(A[r][j], A[i][j]);
}
}
for(int k = 0; k < n; k++){
if(k != i){
for(int j = n; j >= i; j--){
A[k][j] -= A[k][i] / A[i][i] * A[i][j];
}
}
}
}
} int main(){
int cas = 0, n, q;
while(~scanf("%d", &n) && n){
for(int i = 0; i <= n; i++){
g[i].clear();
}
int u, v;
while(scanf("%d %d", &u, &v) && u && v){
u--;
v--;
g[u].push_back(v);
}
memset(f, 0, sizeof(f));
for(int i = 0; i < n; i++){
f[i][i] = -1;
for(int j = 0; j < g[i].size(); j++){
f[g[i][j]][i] += 1.0 / (double)g[i].size();
}
}
f[0][n] = -1;
gauss(f, n);
memset(inf, 0, sizeof(inf));
for(int i = n - 1; i >= 0; i--){
if(abs(f[i][i]) < eps && abs(f[i][n]) > eps){
inf[i] = 1;
}
for(int j = i + 1; j < n; j++){
if(inf[j] && abs(f[i][j]) > eps){
inf[i] = 1;
break;
}
}
}
printf("Case #%d:\n", ++cas);
scanf("%d", &q);
while(q--){
int u;
scanf("%d", &u);
u--;
if(inf[u]){
printf("infinity\n");
}else{
printf("%.3f\n", (abs(f[u][u]) < eps )? 0.0 : abs(f[u][n] / f[u][u]));
}
} }
return 0;
}