首页 > 代码库 > 【BZOJ-3143】游走 高斯消元 + 概率期望
【BZOJ-3143】游走 高斯消元 + 概率期望
3143: [Hnoi2013]游走
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2264 Solved: 987
[Submit][Status][Discuss]
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。
Source
非官方数据
Solution
和 博物馆 那道题类似，列期望方程高斯消元得解。
如果对边进行处理，复杂度是$O((N^{2})^{3})$的，所以考虑利用点来求解边。
设未知数$X_{i}$表示第$i$号点的期望经过次数。那么显然有$X_{i}=\sum X_{j}$这样就可以列方程了。
显然有两个特例，必然从$1$号点出发，所以$X_{1}-1=\sum X_{j}$，以及必然从$N$号点结束，所以$X_{N}=0$，其余的可以得解。
对于一条边$<u,v>$，经过这条边的期望次数就是$\frac {X_{u}} {d[u]}+\frac {X_{v}}{d[v]}$，总期望最小，就是期望次数越小的边标号越大即可。
Code
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}#define MAXN 550#define eps 1e-5int N,M,mp[MAXN][MAXN],flag,d[MAXN];double a[MAXN][MAXN],X[MAXN],p[MAXN*MAXN],ans;inline void Debug(){ puts("========="); for (int i=1; i<=N; i++,puts("")) for (int j=1; j<=N+1; j++) printf("%.2lf ",a[i][j]); puts("");}inline void Gauss(){ flag=1; for (int i=1; i<=N; i++) { int mx=i; for (int j=i+1; j<=N; j++) if (abs(a[j][i])>abs(a[mx][i])) mx=j; swap(a[i],a[mx]); if (abs(a[i][i])<eps) {flag=-1; continue;} for (int j=i+1; j<=N+1; j++) if (abs(a[i][j])>0) a[i][j]/=a[i][i]; a[i][i]=1.0; for (int j=i+1; j<=N; j++) { for (int k=i+1; k<=N+1; k++) a[j][k]-=a[j][i]*a[i][k]; a[j][i]=0.0; }// Debug(); } for (int i=1,f=1; i<=N; i++,f=1) { for (int j=1; j<=N && f; j++) if (abs(a[i][j])>eps) f=0; if (abs(a[i][M+1])>eps && f) flag=0; } if (flag==0) return; for (int i=N; i>=1; i--) { X[i]=a[i][N+1]; for (int j=i+1; j<=N; j++) X[i]-=X[j]*a[i][j]; }}int main(){ N=read(),M=read(); for (int i=1,x,y; i<=M; i++) x=read(),y=read(),mp[x][y]=mp[y][x]=1,d[x]++,d[y]++; for (int i=1; i<=N-1; i++) for (int j=1; j<=N-1; j++) if (mp[i][j]) a[i][j]=-1.0/d[j]; a[1][N+1]=1.0; for (int i=1; i<=N; i++) a[i][i]=1.0;// Debug(); Gauss(); for (int i=1,tot=0; i<=N; i++) for (int j=i+1; j<=N; j++) if (mp[i][j]) p[++tot]=X[i]/d[i]+X[j]/d[j]; sort(p+1,p+M+1);// for (int i=1; i<=M; i++) printf("%.2lf ",p[i]); puts(""); for (int i=1; i<=M; i++) ans+=p[i]*(M-i+1); printf("%.3lf\n",ans); return 0;}
【BZOJ-3143】游走 高斯消元 + 概率期望
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。