【HNOI2013】游走

【HNOI2013】游走

---

概率与期望的神奇姿势？？？？？

这题主要是高消别打错了

让窝口胡一下

首先这个人是可以在一条边上反复横跳无限来回走的，所以直接算肯定算不出

考虑计算每条边被经过的期望次数(g[])，算出来以后sort一遍贪心即可AC此题

然而每条边的期望次数并不好算，在考虑每个点的期望次数(f[])

得转移方程1

[g[(u,v)]=frac{f[u]}{d[u]}+frac{f[v]}{d[v]} ]

(d[])即deg，每个点的度数。

现在考虑如何求(f[])

每个点都能由它的相邻节点转移过来，注意1和n的特殊情况

[f[u]=sum_{(u,v)in mathbb E,v eq n}frac{f[v]}{d[v]} ]

[f[1]=1 ]

所以能列出n个方程，高消解决

（代码虽然答案无误但过程有误，请小心

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
using namespace std;
typedef long long ll;
il int gi(){
	rg int x=0,f=1;rg char ch=getchar();
	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int maxn=501,maxm=233333;
int n,m,fir[maxn],nxt[maxm],dis[maxm],d[maxn],idx;
il vd link(int x,int y){nxt[++idx]=fir[x],fir[x]=idx,dis[idx]=y,++d[x];}
double eq[501][501],f[501],g[maxm];
int main(){
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	n=gi(),m=gi();
	int x,y;while(m--)x=gi(),y=gi(),link(x,y),link(y,x);
	eq[1][n+1]=1;eq[n][n]=-1;
	for(rg int i=1;i<n;++i){
		eq[i][i]=-1;
		for(rg int j=fir[i];j;j=nxt[j])eq[dis[j]][i]=1.0/d[i];
	}
	for(rg int i=1;i<=n;++i){
		for(rg int j=i+1;j<=n;++j)
			for(rg int k=n+1;k>=i;--k)
				eq[j][k]-=eq[i][k]*eq[j][i]/eq[i][i];
	}
	for(rg int i=n;i;--i){
		for(rg int j=i+1;j<=n;++j)eq[i][n+1]-=f[j]*eq[i][j];
		f[i]=eq[i][n+1]/eq[i][i];
	}
	idx=0;
	for(rg int i=1;i<=n;++i)
		for(rg int j=fir[i];j;j=nxt[j])
			if(i<dis[j]){
				++idx;x=i,y=dis[j];
				if(x^n)g[idx]+=f[x]/d[x];
				if(y^n)g[idx]+=f[y]/d[y];
			}
	sort(g+1,g+idx+1);
	double ans=0;
	for(rg int i=1;i<=idx;++i)ans+=g[i]*(m-i+1);
	printf("%.3lf
",ans);
	return 0;
}