这个还挺友好的,自己相对轻松能想出来~
令 $f[i]$ 表示起点到点 $i$ 的期望次数,则 $ans[i]=f[i]\times \frac{p}{q}$

#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 305
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
int edges;
double f[N][N];
int deg[N],hd[N],to[N*N],nex[N*N];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void Gauss(int n)
{
int i,j,k,now;
for(i=1;i<=n;++i)
{
now=i;
for(j=i;j<=n;++j)
{
if(fabs(f[j][i])>fabs(f[now][i])) now=j;
}
if(now!=i)
{
for(j=1;j<=n;++j) swap(f[i][j],f[now][j]);
}
if(f[i][i])
{
for(j=i+1;j<=n+1;++j) f[i][j]/=f[i][i];
f[i][i]=1;
}
for(j=i+1;j<=n;++j)
{
double div=f[j][i];
for(k=i+1;k<=n+1;++k) f[j][k]-=div*f[i][k];
f[j][i]=0;
}
}
for(i=n;i>=1;--i)
{
for(j=i+1;j<=n;++j)
{
f[i][n+1]-=f[j][n+1]*f[i][j];
}
}
}
int main()
{
// setIO("input");
int n,m,p,q,i,j;
double in,out;
scanf("%d%d%d%d",&n,&m,&p,&q);
in=1.0*(double)(1.0*p/q),out=1.0-in;
for(i=1;i<=m;++i)
{
int a,b;
scanf("%d%d",&a,&b),add(a,b),add(b,a),++deg[a],++deg[b];
}
f[1][n+1]=1;
for(i=1;i<=n;++i)
{
f[i][i]=1;
for(j=hd[i];j;j=nex[j])
{
int v=to[j];
f[i][v]=-((1.0/deg[v])*out);
}
}
Gauss(n);
for(i=1;i<=n;++i)
{
printf("%.9f\n",f[i][n+1]*in);
}
return 0;
}

  

最新文章

  1. 《开源安全运维平台OSSIM最佳实践》
  2. Android 解压boot.img
  3. 设计模式——设计模式之禅day1
  4. DateTime格式大全
  5. &lt;密码的实现&gt;输入密码的时候,显示“*”,而不是显示输入内容
  6. 关闭discuzX3.2注册页面的注册邮箱验证
  7. Python 简单聊天室
  8. 测者的性能测试手册:Web压力测试工具webbench
  9. 简述openstack
  10. TensorFlow从入门到理解(四):你的第一个循环神经网络RNN(分类例子)
  11. mysql之Navicat工具、pymysql模块
  12. JS浏览器Session存取数据
  13. nodejs图像处理模块
  14. 遇见C++ Lambda
  15. mysql 开发基础系列3
  16. 视音频数据处理入门:H.264视频码流解析
  17. 使用Base64进行string的加密和解密
  18. Excel---导出与读取(大数据量)
  19. Suffix(hash+lcp+二分)
  20. laravel里面的一些变量

热门文章

  1. Firebase Chat (firebase 实现web聊天室)
  2. Mysql 三大特性详解
  3. 【Havel 定理】Degree Sequence of Graph G
  4. Annotation Type ManyToMany-&gt;&gt;&gt;&gt;&gt;Oracle
  5. 使用tqdm实现下载文件进度条
  6. 并不对劲的bzoj4945:loj2305:uoj317:p3825[NOI2017]游戏
  7. 随便----js参考书
  8. div布局(持续更新)
  9. wpf menuitem 简约显示的 template样式
  10. 深入理解hive(1)