记录编号	380440	评测结果	AAAAAAAAAA
题目名称	[UVa 10828] 随机程序	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.089 s
提交时间	2017-03-09 13:46:25	内存使用	0.39 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <cmath>
#include <vector>
using namespace std;
const double eps = 1e-8;
const int MAXN = 102;
typedef double matrix[MAXN][MAXN];
void gauss_jordan(matrix A, int n){
  for(int i = 0; i < n; i++){
    int r = i;
    for(int j = i+1; j < n; j++)if(fabs(A[j][i]) > fabs(A[r][i]))r = j;
    if(fabs(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 d[MAXN];
bool inf[MAXN];
vector<int> inu[MAXN];
matrix A;
int main(){
  freopen("backtoKR.in", "r", stdin);
  freopen("backtoKR.out", "w", stdout);
  int kase = 1;
  int n;
  while(scanf("%d", &n) == 1 && n){
    memset(d, 0, sizeof(d));
    for(int i = 0; i < n; i++)inu[i].clear();
    int x, y;
    while(scanf("%d %d", &x, &y) == 2 && x){
      x--, y--;
      d[x]++;
      inu[y].push_back(x);
    }
    memset(A, 0, sizeof(A));
    for(int i = 0; i < n; i++){
      A[i][i] = 1;
      for(int j = 0; j < inu[i].size(); j++){
        A[i][inu[i][j]] -= 1.0 / d[inu[i][j]];
      }
      if(!i)A[i][n] = 1;
    }
    gauss_jordan(A, n);
    memset(inf, false, sizeof(inf));
    for(int i = n-1; ~i; i--){
      if(fabs(A[i][i]) < eps && fabs(A[i][n]) > eps)inf[i] = true;
      for(int j = i+1; j < n; j++)
        if(fabs(A[i][j]) > eps && inf[j])inf[i] = true;
    }
    int q, u;
    scanf("%d", &q);
    printf("Case #%d:\n", kase++);
    while(q--){
      scanf("%d", &u); u--;
      if(inf[u])puts("infinity");
      else printf("%.3lf\n", fabs(A[u][u]) < eps? 0.0 : A[u][n]/A[u][u]);
    }
  }
  return 0;
}