Problem I
Back to Kernighan-Ritchie
Input: Standard Input
Output: Standard Output
You must have heard the name of Kernighan and Ritchie, the authors of The C Programming Language. While coding in C, we use different control statements and loops, such as, if-then-else, for, do-while, etc. Consider the following fragment of pseudo code:
//execution starts here
do {
U;
V;
} while(condition);
W;
In the above code, there is a bias in each conditional branch. Such codes can be represented by control flow graphs like below:
Let the probability of jumping from one node of the graph to any of its adjacent nodes be equal. So, in the above code fragment, the expected number of times U executes is 2. In this problem, you will be given with such a control flow graph and find the expected number of times a node is visited starting from a specific node.
Input
Input consists of several test cases. There will be maximum 100 test cases. Each case starts with an integer: n (n ≤ 100). Here n is the number of nodes in the graph. Each node in the graph is labeled with 1 to n and execution always starts from 1. Each of the next few lines has two integers: start and end which means execution may jump from node start to node end. A value of zero for start ends this list. After this, there will be an integer q (q ≤ 100) denoting the number of queries to come. Next q lines contain a node number for which you have to evaluate the expected number of times the node is visited. The last test case has value of zero for n which should not be processed.
Output
Output for each test case should start with “Case #i:” with next q lines containing the results of the queries in the input with three decimal places. There can be situations where a node will be visited forever (for example, an infinite for loop). In such cases, you should print “infinity” (without the quotes). See the sample output section for details of formatting.
Sample Input Output for Sample Input
| 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 |
Problem setter: Mohammad Sajjad Hossain
Special Thanks: Shahriar Manzoor
由於期望值
E[j] = sigma(E[i]*(1/deg[i])), if i->j exists.
每方程式展, 因此有 n 方程式, n 一元的未知求解。
由於起始的期望值比特 E[1] = sigma(E[i]*(1/deg[i]))+1大致上就是如此，利用高斯消去法求解每方程式的解。
至於卡在一，算方程式的解，由於分子太小，double 跑到 NaN 去了。
特判一下例子。
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
double sol[105];
int nosol[105];
void gaussianElimination(double mtx[][105], int n) {
#define eps 1e-8
int i, j;
for(i = 1; i <= n; i++) {
int k = i;
for(j = i+1; j <= n; j++)
if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
k = j;
if(fabs(mtx[k][i]) < eps)
continue;
if(k != i) {
for(j = 1; j <= n+1; j++)
swap(mtx[k][j], mtx[i][j]);
}
for(j = 1; j <= n; j++) {
if(i == j) continue;
for(k = n+1; k >= i; k--) {
mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
}
}
}
memset(nosol, 0, sizeof(nosol));
for(i = n; i >= 1; i--) {
if(fabs(mtx[i][n+1]) > eps && fabs(mtx[i][i]) < eps)
nosol[i] = 1;
else {
if(fabs(mtx[i][n+1]) < eps)
sol[i] = 0;
else
sol[i] = mtx[i][n+1]/mtx[i][i];
}
for(j = i+1; j <= n; j++)
if(fabs(mtx[i][j]) > eps && nosol[j])
nosol[i] = 1;
}
}
int main() {
int cases = 0;
int n, x, y, i, j;
while(scanf"%d", &n) == 1 && n) {
vector<int> invg[105];
int deg[105] = {};
while(scanf("%d %d", &x, &y) == 2) {
if(x == 0 && y == 0)
break;
deg[x]++;
invg[y].push_back(x);
}
double mtx[105][105];
memset(mtx, 0, sizeof(mtx));
mtx[1][n+1] = 1;
for(i = 1; i <= n; i++) {
mtx[i][i] = 1;
for(j = 0; j < invg[i].size(); j++)
mtx[i][invg[i][j]] -= 1.0/deg[invg[i][j]];
}
gaussianElimination(mtx, n);
printf("Case #%d:\n", ++cases);
scanf("%d", &x);
while(x--) {
scanf("%d", &y);
if(nosol[y])
puts("infinity");
else
printf("%.3lf\n", sol[y]);
}
}
return 0;
}
/*
E[j] = sigma(E[i]*(1/deg[i])), if i->j exists.
*/
