BZOJ 1778: [Usaco2010 Hol]Dotp 驱逐猪猡 概率与期望+高斯消元
2024-09-04 11:26:55
这个还挺友好的,自己相对轻松能想出来~
令 $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;
}
最新文章
- 《开源安全运维平台OSSIM最佳实践》
- Android 解压boot.img
- 设计模式——设计模式之禅day1
- DateTime格式大全
- <;密码的实现>;输入密码的时候,显示“*”,而不是显示输入内容
- 关闭discuzX3.2注册页面的注册邮箱验证
- Python 简单聊天室
- 测者的性能测试手册:Web压力测试工具webbench
- 简述openstack
- TensorFlow从入门到理解(四):你的第一个循环神经网络RNN(分类例子)
- mysql之Navicat工具、pymysql模块
- JS浏览器Session存取数据
- nodejs图像处理模块
- 遇见C++ Lambda
- mysql 开发基础系列3
- 视音频数据处理入门:H.264视频码流解析
- 使用Base64进行string的加密和解密
- Excel---导出与读取(大数据量)
- Suffix(hash+lcp+二分)
- laravel里面的一些变量
热门文章
- Firebase Chat (firebase 实现web聊天室)
- Mysql 三大特性详解
- 【Havel 定理】Degree Sequence of Graph G
- Annotation Type ManyToMany->;>;>;>;>;Oracle
- 使用tqdm实现下载文件进度条
- 并不对劲的bzoj4945:loj2305:uoj317:p3825[NOI2017]游戏
- 随便----js参考书
- div布局(持续更新)
- wpf menuitem 简约显示的 template样式
- 深入理解hive(1)