bzoj 3143: [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

Sample Output

HINT

Source

非官方数据

题解：概率与期望+高斯消元

期望=概率*权值。

我们必然是希望概率大的分配的权值尽量小。

那么问题其实就变成了如何求解一条边的概率。对于边v(x,y) E(v)=(x!=n?E(x)*p[out[x]])+(y!=n?E(y)*p[out[y]] 其中p表示选择这条边出去的概率。为什么x,y不能是n呢？因为到达n后游走就结束了，必然不会再出来了。

对于点的概率，我们可以列方程组求解。1号点需要特别注意，因为刚开始是从1出发的，所以1号点的初始概率是1，但是这并不是最后的概率，因为起点是可以重复经过的，所以还会有再次到达的概率。

E(1)-sigma((x,1)属于边集）p[out[x]]*E[x]=1

对于终点，他是不会有出边的，所以我们建矩阵的时候需要忽略(n,x)这种边。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 600003#define eps 1e-10using namespace std;double a[510][510],b[N],ans[N],sum;int n,m,tot,nxt[N],point[N],v[N],vx[N],vy[N],num[N],c[N],out[N];struct data{	int x; double val;}a1[N];void add(int x,int y,int i){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; num[tot]=i;	tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; num[tot]=i;}int cmp(data a,data b){	return a.val>b.val;}void guass(int n){	for (int i=1;i<=n;i++) {		int num=i;		for (int j=i+1;j<=n;j++)		 if (fabs(a[j][i])>fabs(a[num][i])) num=j;		if (num!=i) {			for (int j=1;j<=n;j++) swap(a[num][j],a[i][j]);			swap(b[num],b[i]);		}		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=1;k<=n;k++) 			 a[j][k]-=a[i][k]*t;			b[j]-=b[i]*t;		}	}	for (int i=n;i>=1;i--) {		double t=1.0*b[i];		for (int j=i+1;j<=n;j++)		 if (a[i][j]) t-=a[i][j]*ans[j];		ans[i]=t/a[i][i];	}}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	for (int i=1;i<=m;i++) {		int x,y; scanf("%d%d",&x,&y);		add(x,y,i); out[x]++; out[y]++;		vx[i]=x; vy[i]=y;			}	for (int i=1;i<=n;i++) {		if (i==1) b[i]=1;		a[i][i]=1;		for (int j=point[i];j;j=nxt[j]){			if (v[j]==n) continue;			double t=1.0/out[v[j]];			a[i][v[j]]-=t;		}    }	guass(n);	for (int i=1;i<=m;i++) {		a1[i].x=i; 		if (vx[i]!=n) a1[i].val+=ans[vx[i]]*(1.0/out[vx[i]]);		if (vy[i]!=n) a1[i].val+=ans[vy[i]]*(1.0/out[vy[i]]);	}	sort(a1+1,a1+m+1,cmp); sum=0;	for (int i=1;i<=m;i++) sum+=(double)i*a1[i].val;	PRintf("%.3lf/n",sum+eps);}