首页 > 代码库 > [Luogu P2973&BZOJ 1778][USACO10HOL]赶小猪DOtP（高斯消元+期望）
[Luogu P2973&BZOJ 1778][USACO10HOL]赶小猪DOtP（高斯消元+期望）
Description
一个无向图，节点1有一个炸弹，在每个单位时间内，有可能在这个节点炸掉，也有p/q的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。
Solution
没错它就是BZOJ 1778…在bzoj上是权限题
炸弹最终爆炸的概率是1（可能是在无穷无尽的时间之后…），于是到达某一点的概率除以到达所有点的概率就是在这个节点上爆炸的概率
f[u]=∑f[v]*(1-p/q)/d[v]
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;int n,m,d[303],head[303],cnt=0;double a[303][303],f[303],p,q;struct Node{ int next,to;}Edges[100005];void addedge(int u,int v){ Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v;}void Gauss(){ for(int i=1;i<=n;i++) { int maxline=i; for(int j=i;j<=n;j++) if(a[j][i]>a[maxline][i])maxline=j; if(maxline!=i) for(int j=i;j<=n+1;j++) swap(a[maxline][j],a[i][j]); for(int j=i+1;j<=n;j++) { double t=a[j][i]/a[i][i]; for(int k=i;k<=n+1;k++) a[j][k]-=t*a[i][k]; } } for(int i=n;i>0;i--) { for(int j=n;j>i;j--) a[i][n+1]-=f[j]*a[i][j]; f[i]=a[i][n+1]/a[i][i]; }}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d%lf%lf",&n,&m,&p,&q); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); d[u]++,d[v]++; } for(int i=1;i<=n;i++) { a[i][i]+=1; for(int j=head[i];~j;j=Edges[j].next) { int v=Edges[j].to; a[v][i]-=(1-p/q)/d[i]; } } a[1][n+1]+=1-p/q; Gauss(); double sum=0; for(int i=1;i<=n;i++)sum+=f[i]; for(int i=1;i<=n;i++) printf("%.9lf\n",f[i]/sum); return 0;}
[Luogu P2973&BZOJ 1778][USACO10HOL]赶小猪DOtP（高斯消元+期望）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。