数学期望/高斯消元/马尔可夫过程

  刘汝佳老师白书上的例题- -b

  本体不满足拓扑关系,但马尔可夫过程是可以高斯消元解的……

  用「高斯·约当消元」更方便!

 //UVA 10828
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*=sign;
}
const int N=;
const double eps=1e-;
typedef double Matrix[N][N];
/******************tamplate*********************/ void gauss_jordan(Matrix A,int n){
int i,j,k,r;
rep(i,n){
r=i;
for(j=i+;j<n;++j)
if (fabs(A[j][i]) > fabs(A[r][i])) r=j;
if (fabs(A[r][i]) < eps)continue;
if (r!=i) F(j,,n) swap(A[r][j],A[i][j]); rep(k,n) if (k!=i)
D(j,n,i) A[k][j]-=A[k][i]/A[i][i]*A[i][j];
}
}
Matrix A;
int n,d[N];
vector<int> pre[N];
bool inf[N]; int main(){
#ifndef ONLINE_JUDGE
freopen("10828.in","r",stdin);
freopen("10828.out","w",stdout);
#endif
int cs=;
while(scanf("%d",&n)== && n){
memset(d,,sizeof d);
rep(i,n) pre[i].clear();
int a,b;
while(scanf("%d%d",&a,&b)== && a && b){
a--; b--;
d[a]++;
pre[b].pb(a);
}
memset(A,,sizeof (A));
rep(i,n){
A[i][i]=;
rep(j,pre[i].size())
A[i][pre[i][j]]-=1.0/d[pre[i][j]];
if (i==) A[i][n]=;
} gauss_jordan(A,n);
memset(inf,,sizeof inf);
for(int i=n-;i>=;i--){
if ( fabs(A[i][i])<eps && fabs(A[i][n])>eps ) inf[i]=;
for(int j=i+;j<n;j++)
if (fabs(A[i][j])>eps && inf[j]) inf[i]=;
} int q,u;
scanf("%d",&q);
printf("Case #%d:\n",++cs);
while(q--){
scanf("%d",&u); u--;
if (inf[u]) printf("infinity\n");
else printf("%.3lf\n",fabs(A[u][u]) < eps ? 0.0 : A[u][n]/A[u][u]);
}
}
return ;
}

最新文章

  1. svn迁移gitlab,构建前端打包发布流程
  2. passive 的事件监听器
  3. svn 版本控制
  4. ASP.NET Core (Database First)
  5. The specified framework &#39;Microsoft.NETCore.App&#39;, version &#39;1.0.1&#39; was not found 解决办法
  6. NUC_HomeWork1 -- POJ2067(最短路)
  7. 快乐的JS正则表达式(二)
  8. Android之ScrollView
  9. DataGridView显示行号的几种方法来自http://www.soaspx.com/dotnet/csharp/csharp_20100204_2740.html
  10. Android setTextColor无效_安卓setTextColor()的参数设置方式
  11. GTK+2.0学习——第一个GTK程序
  12. Spring学习笔记6——注解方式测试
  13. Thermostat:双层存储结构的透明巨页内存管理机制
  14. LeetCode 100. Same Tree 判断两棵二叉树是否相等 C++
  15. java使用c3p0连接mysql,写中文数据乱码的问题
  16. TensorFlow+Keras 03 TensorFlow 与 Keras 介绍
  17. MT【165】分段函数
  18. python文件写中的f.flush()方法
  19. JavaScript设计模式系列学习笔记目录
  20. python 切片&amp;迭代

热门文章

  1. Js判断CSS文件加载完毕的实例教程
  2. 一些常用css技巧的为什么(二)我所理解的line-height
  3. 三款精美的html5及css3的源码插件
  4. debian终端菱形乱码修复
  5. Excel中 设置使得每行的颜色不一样
  6. extern 数组
  7. TextEdit验证
  8. JS对select动态添加options操作[IE&amp;FireFox兼容]
  9. Redis源码研究--启动过程
  10. 基于PinnedSectionListView实现联系人通讯录并且点击打电话