[关闭]
@ysner 2018-03-30T17:21:19.000000Z 字数 1767 阅读 2107

[HNOI2013]游走

期望 高斯消元


题面

一个无向连通图,顶点从1编号到N,边从1编号到M。 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。


解析

要使值最小,就让经过越大的边标号越小。
那么就要求边的概率。

为点概率,为边概率,为点度数。

于是要求点的概率。
点的概率为相邻点转移到自己的概率。

待会,求当前点概率就要用到邻点概率,求邻点概率就要用到当前点概率,这没法DP啊。
但我们可以发现一个表达式:(
(出发点自身就有概率为1)
这不很像一个一元一次方程?据此可解得

还有些细节,代码里应该有注释。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<algorithm>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=600;
  15. int n,m,h[N*N<<1],cnt,in[N],st[N*N<<1],ed[N*N<<1];
  16. double dp[N][N],ans,x[N],E[N*N<<1];
  17. struct Edge
  18. {
  19. int to,next;
  20. }e[N*N<<1];
  21. il void add(re int u,re int v)
  22. {
  23. e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
  24. }
  25. il int gi()
  26. {
  27. re int x=0,t=1;
  28. re char ch=getchar();
  29. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  30. if(ch=='-') t=-1,ch=getchar();
  31. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  32. return x*t;
  33. }
  34. il void Gauss()
  35. {
  36. fp(i,1,n)
  37. fp(j,i+1,n)
  38. fq(k,n+1,i) dp[j][k]-=dp[i][k]*dp[j][i]/dp[i][i];
  39. fq(i,n,1)
  40. {
  41. x[i]=dp[i][n+1];
  42. fq(j,n,i+1) x[i]-=dp[i][j]*x[j];
  43. x[i]/=dp[i][i];
  44. }
  45. }
  46. int main()
  47. {
  48. memset(h,-1,sizeof(h));
  49. n=gi();m=gi();
  50. fp(i,1,m)
  51. {
  52. re int u=gi(),v=gi();add(u,v);add(v,u);in[u]++;in[v]++;st[i]=u;ed[i]=v;
  53. }
  54. fp(i,1,n-1)
  55. {
  56. dp[i][i]=1;
  57. for(re int j=h[i];j+1;j=e[j].next)
  58. {
  59. re int v=e[j].to;//j->i???
  60. if(v!=n) dp[i][v]-=1.0/in[v];//概率不能从n转移,写1.0而不是1!!!
  61. }
  62. }
  63. dp[1][n+1]=1;//钦定第一个点概率为1
  64. dp[n][n]=1;
  65. Gauss();
  66. fp(i,1,m) E[i]=x[st[i]]/in[st[i]]+x[ed[i]]/in[ed[i]];
  67. sort(E+1,E+1+m);
  68. fp(i,1,m) ans+=E[i]*(m-i+1);
  69. printf("%.3lf\n",ans);
  70. return 0;
  71. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注