记录编号	86048	评测结果	AAAAAAAAAA
题目名称	[UVa 10828] 随机程序	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.107 s
提交时间	2014-01-19 22:15:58	内存使用	0.41 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
//下标从0开始
const int SIZEN=110;
const double eps=1e-8;
void Gauss_Jordan(double A[SIZEN][SIZEN],int n){//A就是增广矩阵,n行n+1列
	int i,j,k,r;
	for(i=0;i<n;i++){
		r=i;
		for(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(j=0;j<=n;j++) swap(A[r][j],A[i][j]);
		for(k=0;k<n;k++){
			if(k!=i){
				for(j=n;j>=i;j--) A[k][j]-=A[k][i]/A[i][i]*A[i][j];
			}
		}
	}
}
void solve(double A[SIZEN][SIZEN],int n,int kase){//解答A描述的方程,共n个变量
	//kase表示当前是第几组数据,quest是请求个数
	Gauss_Jordan(A,n);
	bool infinity[SIZEN]={0};
	int i,j;
	for(i=n-1;i>=0;i--){
		if(fabs(A[i][i])<eps&&fabs(A[i][n])>eps) infinity[i]=true;
		for(j=i+1;j<n;j++) if(fabs(A[i][j])>eps&&infinity[j]) infinity[i]=true;
	}
	int quest,u;
	printf("Case #%d:\n", kase);
	scanf("%d",&quest);
	while(quest--){
		scanf("%d",&u);
		u--;
		if(infinity[u]) printf("infinity\n");
		else printf("%.3lf\n",fabs(A[u][u])<eps?0.0:A[u][n]/A[u][u]);
	}
}
int N;
double A[SIZEN][SIZEN]={0};
double deg[SIZEN]={0};
vector<int> tc[SIZEN];//反邻接表
bool init(void){
	scanf("%d",&N);
	if(!N) return false;
	memset(A,0,sizeof(A));
	memset(deg,0,sizeof(deg));
	int a,b,i,j;
	for(i=0;i<N;i++) tc[i].clear();
	while(true){
		scanf("%d%d",&a,&b);//a指向b
		if(!a&&!b) break;
		a--,b--;
		deg[a]++;
		tc[b].push_back(a);
	}
	for(i=0;i<N;i++){
		A[i][i]=1;
		for(j=0;j<tc[i].size();j++) A[i][tc[i][j]]-=1.0/deg[tc[i][j]];
	}
	A[0][N]=1;//因为总是从节点0开始执行
	return true;
}
int main(){
	freopen("backtoKR.in","r",stdin);
	freopen("backtoKR.out","w",stdout);
	int kase=0;
	while(init()) solve(A,N,++kase);
	return 0;
}