【BZOJ3143】[Hnoi2013]游走 期望DP+高斯消元
DP 期望 高斯消 游走
2023-09-11 14:15:27 时间
【BZOJ3143】[Hnoi2013]游走
Description
一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。
Input
第一行是正整数N和M,分别表示该图的顶点数 和边数,接下来M行每行是整数u,v(1≤u,v≤N),表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10,100%的数据满足2≤N≤500且是一个无向简单连通图。
Output
仅包含一个实数,表示最小的期望值,保留3位小数。
Sample Input
3 3
2 3
1 2
1 3
2 3
1 2
1 3
Sample Output
3.333
HINT
边(1,2)编号为1,边(1,3)编号2,边(2,3)编号为3。
题解:一个清晰的思路:我们如果能求出每条边期望被经过的次数,然后排个序,让期望次数越大的边的编号越小就行了。但是问题来了,点数500,边数?????,以边为变量跑高斯消元显然会TLE,那么我们只能以点为变量跑高斯消元。那么如何用点的期望表示边的期望呢?其实很简单,设边(a,b),点a的期望被经过次数是f[a],点b的是f[b],a的度数是d[a],b的是d[b],那么这条边的期望被经过次数显然是${f[a]\over d[a]}+{f[b]\over d[b]}$。
然后就是老办法了,如果存在边(a,b),那就f[a]+=f[b]/d[b],处理出来再移项即可,直接上高斯消元。
别忘了f[n]=1,f[1]要+1(因为是起始点)
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long double ld; int n,m; int pa[130000],pb[130000],d[510]; ld pc[130000],v[510][510],ans; void add(int a,int b) { if(a==n) return ; v[b][a]-=(ld)1/d[a]; } int main() { scanf("%d%d",&n,&m); int i,j,k; for(i=1;i<=m;i++) scanf("%d%d",&pa[i],&pb[i]),d[pa[i]]++,d[pb[i]]++; for(i=1;i<=m;i++) add(pa[i],pb[i]),add(pb[i],pa[i]); for(i=1;i<=n;i++) v[i][i]+=1; for(i=1;i<=n+1;i++) v[n][i]=0; v[n][n]=v[n][n+1]=1,v[1][n+1]+=1; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) if(fabs(v[j][i])>fabs(v[i][i])) for(k=i;k<=n+1;k++) swap(v[i][k],v[j][k]); if(fabs(v[i][i])<1e-7) continue; for(j=n+1;j>=i;j--) v[i][j]/=v[i][i]; for(j=1;j<=n;j++) if(i!=j) { for(k=1;k<=n+1;k++) if(i!=k) v[j][k]-=v[j][i]*v[i][k]; v[j][i]=0; } } for(i=1;i<=m;i++) { if(pa[i]!=n&&fabs(v[pa[i]][pa[i]])>1e-7) pc[i]+=v[pa[i]][n+1]/d[pa[i]]; if(pb[i]!=n&&fabs(v[pb[i]][pb[i]])>1e-7) pc[i]+=v[pb[i]][n+1]/d[pb[i]]; } sort(pc+1,pc+m+1); for(i=1;i<=m;i++) ans+=(m-i+1)*pc[i]; printf("%.3lf",(double)ans); return 0; }
相关文章
- bfs+状态压缩dp
- hdu 5375 - Gray code(dp) 解题报告
- 【DP】ABC281 D - Max Multiple
- 【区间DP】取数游戏
- 【简单DP】[NOIP2007 普及组] 守望者的逃离
- 【Kuangbin简单DP】平整数组
- 【POJ 3071】 Football(DP)
- 【BZOJ4606】[Apio2008]DNA DP
- 【BZOJ2616】SPOJ PERIODNI 笛卡尔树+树形DP
- 【BZOJ4321】queue2 DP
- 【BZOJ3566】[SHOI2014]概率充电器 期望+树形DP
- 【BZOJ1778】[Usaco2010 Hol]Dotp 驱逐猪猡 期望DP+高斯消元
- 【BZOJ2337】[HNOI2011]XOR和路径 期望DP+高斯消元
- [NOIP2016]换教室 D1 T3 Floyed+期望DP
- 【BZOJ3450】Tyvj1952 Easy 期望DP
- UVa 11427 Expect the Expected (数学期望 + 概率DP)
- BZOJ 1026 [SCOI2009]windy数 (数位DP)
- UVa 12093 Protecting Zonk (树形DP)
- LightOJ 1248 Dice (III) (水题,期望DP)
- UVaLive 10859 Placing Lampposts (树形DP)
- HDU 3944 DP? (Lucas定理)
- HDU 4352 XHXJ's LIS (数位DP+LIS+状态压缩)
- POJ 3176 Cow Bowling (水题DP)
- 【CodeForces 261B】Maxim and Restaurant(DP,期望)
- 【bzoj5197】[CERC2017]Gambling Guide 期望dp+堆优化Dijkstra
- 【bzoj4903/uoj300】[CTSC2017]吉夫特 数论+状压dp
- 【bzoj2423】[HAOI2010]最长公共子序列 dp
- 【bzoj4318】OSU! 期望dp
- 【codevs1163】访问艺术馆 树形dp