有后效性的DP:$f[u]$表示到$u$的期望次数,$f[u]=\Sigma_{(u,v)} (1-\frac{p}{q})*f[v]*deg[v]$,最后答案就是$f[u]*p/q$

刚开始$f[1]=1$,,因为炸弹初始在$1$号节点。所以增广矩阵中$a[1][n+1]=1$。

系数矩阵$a[i][i]$赋值为1,其他点的系数写成负数,相当于是所有的加起来$=0$.

#include<cstdio>
#include<iostream>
#include<cmath>
#define R register int
#define db long double
using namespace std;
const db eps=1E-;
const int N=;
db a[N][N],P;
int mp[N][N],r[N],n,m,p,q;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
inline bool ck0(const db& x) {return x<eps&&x>-eps;}
inline void Gauss(int n) {
for(R i=;i<=n;++i) { R p=i;
for(R j=i+;j<=n;++j) if(ck0(a[p][i])||fabs(a[p][i])<fabs(a[j][i])) p=j;
if(p!=i) swap(a[p],a[i]);
for(R j=i+;j<=n;++j) if(!ck0(a[j][i])) {
register db t=a[j][i]/a[i][i];
for(R k=;k<=n+;++k) a[j][k]-=t*a[i][k];
}
} for(R i=n;i>=;--i) {
for(R j=n;j>i;--j) a[i][n+]-=a[i][j]*a[j][n+];
a[i][n+]/=a[i][i];
}
}
signed main() {
n=g(),m=g(),p=g(),q=g(); P=(db)p/q;
for(R i=,u,v;i<=m;++i) u=g(),v=g(),mp[u][v]=mp[v][u]=,++r[u],++r[v];
for(R i=;i<=n;++i) a[i][i]=;
for(R i=;i<=n;++i) for(R j=;j<=n;++j) if(mp[i][j]) a[i][j]-=(1.0-P)/r[j];
a[][n+]=; Gauss(n); for(R i=;i<=n;++i) printf("%.9Lf\n",a[i][n+]*P);

2019.05.24

最新文章

  1. PHP获取当前服务器信息的基本语句
  2. Python的包管理工具Pip (zz )
  3. boost 编译,windows平台
  4. LoadRunner支持的IE版本
  5. Oracle DBWR,LGWR,CKPT,ARCH 触发条件 总结
  6. 【模拟ACM排名】ZOJ-2593 Ranking (Andrew Stankevich’s Contest #5)
  7. app开发历程——android手机显示服务器端图片思路
  8. 触发器实现对插入数据的字段更改 Oracle+SQL Server
  9. MySQL5.6生产库自动化安装部署
  10. SpringMVC源码之参数解析绑定原理
  11. 华为7.0系统最简单激活xposed框架的流程
  12. 防止Web表单重复提交的方法总结
  13. 快速排序 Java实现的快速排序
  14. css3-盒模型新增属性
  15. centos远程连接putty工具配置
  16. VS Installer教程
  17. java使用代理模拟http get请求
  18. Maven .m2\repository\jdk\tools\1.7 missing
  19. win8共享文件设置 详细教程
  20. TP v5中Request取值方式变化

热门文章

  1. Spring MVC表单提交
  2. bzoj 4822~4824 CQOI2017题解
  3. chrome中的content script脚本文件
  4. 如何使用ODB(How to use odb On windows)
  5. jQuery常用ajax操作
  6. Poj 2017 Speed Limit(水题)
  7. 在Global Azure上用Azure CLI创建ARM的VM和面向公网的负载均衡
  8. Scala总结
  9. Unreal引擎术语表
  10. MVC4.0 里的分析器错误