bzoj 3143: [Hnoi2013]游走 （概率与期望+高斯消元）

3143: [Hnoi2013]游走

Time Limit: 10 Sec   Memory Limit: 128 MB

Submit: 2651   Solved: 1143

[ 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

Sample Output

3.333

HINT

边 (1,2) 编号为 1 ，边 (1,3) 编号 2 ，边 (2,3) 编号为 3 。

Source

非官方数据

[ Submit][ Status][ Discuss]

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

期望=概率*权值。

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

那么问题其实就变成了如何求解一条边的概率。对于边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-10
using 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);
}