OI题库

【题目描述】

你一定听说过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