1495. [UVa 10828] 随机程序

【题目描述】

你一定听说过Kernighan和Ritchie，他们是《C程序设计语言》的作者。当在C语言中编程时，我们使用不同的控制语句和循环。例如,if-then-else（原文如此——译者注）,for,do-while等等。考虑如下伪代码：

//execution starts here
do {
	U;
	V;
} while(condition);
W;

在上述代码中，每个分支都有一定的执行条件。这一代码可以用流程图表示如下：

对每个节点，令其转到任意后继的概率相等。因此，在上面的代码中，U执行的期望次数是2.在这个问题中，给出这样的一个流程图，请你找出每个节点的期望执行次数。

【输入格式】

输入包含至多100组数据。

每组数据的第1行是一个正整数n(1<=n<=100)。n是流程图中的节点个数。节点被从1到n编号，并且总是从1开始执行。

下面有若干行，每行2个正整数：start和end，意味着执行完start后可以转到end。以2个0结束。

下面一行有一个正整数q(1<=q<=100)，描述询问个数。

接下来的q行，每行一个正整数x，意味着询问节点x的期望执行次数。

输入文件以n=0结束。

【输出格式】

对第i组数据：

先输出一行"Case #i:"。

接下来输出q行，每行1个实数，表示该查询对应的期望次数。保留三位小数。某个节点有可能被永远执行（例如，一个无穷的for循环）。对于这种情况，输出"infinity"。

具体格式见样例。

【样例输入】

3
1 2
2 3
2 1
0 0
3
1
2
3
3
1 2
2 3
3 1
0 0
3
3
2
1
0

【样例输出】

Case #1:
2.000
2.000
1.000
Case #2:
infinity
infinity
infinity

【提示】

使用计算机中的“保留3位小数”指令。假设你的计算机能正确进行舍入。

【来源】

UVa10828 Back to Kernighan-Ritchie

刘汝佳，《算法竞赛入门经典训练指南》表2-12

Problem setter: Mohammad Sajjad Hossain

Special Thanks: Shahriar Manzoor