UVa 10828 Back to Kernighan-Ritchie (高斯-约当消元)

本文主要是介绍UVa 10828 Back to Kernighan-Ritchie (高斯-约当消元)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa 10828 Back to Kernighan-Ritchie

题目大意:

给出一个程序控制流图,从每个结点出发到其后继结点的概率相等.当执行完一个没有后继的结点后,程序终止.程序总是从编号为1的结点开始执行.求出多个询问结点的期望执行次数.
数据不超过100组,第一行为 $n(1\leq n\leq 100)$ ,结点编号为 $1$ 到 $n$ .以下若干行每行包含 $a,b$ 两个整数,以 $a=b=0$ 位结束表示,下一行为 $q$ ,接下来是 $q$ 个询问,每行一个整数,若无解,输出”infinity”.结束标志为 $n=0$ .

题目分析:

设 $i$ 号结点的出度为 $out_i$ ,那么从 $i$ 号结点到其每个后继结点的概率为 $1/out_i$ .
用 $p$ 表示结点的前驱结点,对于每个结点 $u$ 的期望执行次数 $x_u$ ,则有

$x_u=x_{p1}/out_1+x_{p2}/out_2+...+x_{pk}/out_k$

将式子右边的未知数移动到左边

$x_u-x_{p1}/out_1-x_{p2}/out_2-...-x_{pk}/out_k=0$

对于任意一个结点都可以建立一个方程,则可以建立方程组.

当然,由于程序总是从1号点开始,所以可以理解为有一个0号结点后继结点有且仅有1号结点,且 $x_0=1$ .
不过还要判断其是否有解,则若出现 $kx_u=b$ , $k=0$ && $b!=0$ 时, $x_u$ 无解.且若存在 $x_v$ 与 $x_u$ 存在于同一等式中,则 $x_v$ 也无解.

代码:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>using namespace std;const double eps=1e-8;//切记浮点数判断的时候要加上绝对值fabs! 
const int maxn=100+5;
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[r][i])<fabs(A[j][i])) r=i;if(r!=i) for(int j=0;j<n;j++) swap(A[i][j],A[r][i]);if(fabs(A[i][i])<eps) continue;//若|A[i][i]|max=0,放弃操作,作为后续判断是否有解依据 for(int j=0;j<n;j++) if(j!=i)for(int k=n;k>=i;k--)A[j][k]-=A[j][i]/A[i][i]*A[i][k];}
}Matrix A;
vector<int>pre[maxn];//pre[v]表示v点的前驱结点 
int out[maxn],inf[maxn];//out[u]表示u点的出度 void init(int n)
{memset(A,0,sizeof(A));memset(inf,0,sizeof(inf));memset(out,0,sizeof(out));for(int i=0;i<n;i++) pre[i].clear();
}int main()
{int n,a,b,q,u,kase=0;while(scanf("%d",&n)==1&&n) {init(n);while(scanf("%d%d",&a,&b)==2&&a)pre[--b].push_back(--a),++out[a];A[0][n]=1;for(int i=0;i<n;i++) {A[i][i]=1;for(int j=0;j<pre[i].size();j++)A[i][pre[i][j]]=-1.0/out[pre[i][j]];}Gauss_Jordan(A,n);for(int i=0;i<n;i++) {if(A[i][i]<eps&&fabs(A[i][n])>eps) inf[i]=1;//未知数系数为0,常数项不为0,未知数无解 if(inf[i]) for(int j=0;j<n;j++)//凡是涉及到无解未知数的未知数,一样是无解 if(j!=i&&fabs(A[j][i])>eps) inf[j]=1;}scanf("%d",&q);printf("Case #%d:\n",++kase);while(q--) {scanf("%d",&u);if(inf[--u]) printf("infinity\n");else printf("%.3lf\n",fabs(A[u][u])<eps?0:A[u][n]/A[u][u]);//若在有解的前提下,A[u][u]=0;说明无法从起点到达u点,所以其期望为0 }}return 0;
}