首页 > 代码库 > [BZOJ 3143][Hnoi2013]游走（高斯消元+期望）
[BZOJ 3143][Hnoi2013]游走（高斯消元+期望）
Description
一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
Solution
对于点u(u≠1)：到达u的概率 f[u]=∑f[v]/d[v] （Edges(u,v)）
而f[1]=∑f[v]/d[v]+1 (Edges(1,v))
高斯消元可以求出所有点的概率
对于每条边 到达边i的概率 p[i]=f[u]/d[u]+f[v]/d[v]
贪心的编号然后求出期望就好了
好像BZOJ上的数据会比较水，洛谷数据…卡精度
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#define eps 1e-7using namespace std;int n,m,head[505],cnt=0,d[505];double a[505][505],f[505],p[250005];struct Node{ int next,from,to;}Edges[500005];void addedge(int u,int v){ Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].from=u; Edges[cnt].to=v;}void Gauss(){ for(int i=1;i<=n;i++) { int maxline=i; for(int j=i+1;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++) { if(fabs(a[j][i])<eps)continue; 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",&n,&m); 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) a[i][Edges[j].to]=-1.0/d[Edges[j].to]; } a[1][n+1]=1,a[n][n]=1; Gauss(); for(int i=1;i<=cnt;i+=2) { int u=Edges[i].from,v=Edges[i].to; p[(i+1)>>1]+=(double)f[u]/d[u]; p[(i+1)>>1]+=(double)f[v]/d[v]; } sort(p+1,p+1+m); double ans=0; for(int i=1;i<=m;i++) ans+=p[i]*(m-i+1); printf("%.3lf\n",ans); return 0;}
被卡精度）
[BZOJ 3143][Hnoi2013]游走（高斯消元+期望）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。