$$\Large\texttt{My Blog}$$

---

Description

题目链接：Luogu 3232

有一个无向简单连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。

小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和的，答案保留 $3$ 位小数。

现在，请你对这 $m$ 条边进行编号，使得小Z获得的总分的期望值最小。

数据范围：$2\le n\le 500$

---

Solution

由于没有对 $m$ 的范围进行限定，那么 $m$ 的最大值可以达到 $O(n^2)$，这是无法接受的，因此我们考虑先统计点的期望次数。

我们设 $deg_i$ 表示第 $i$ 个点的度数，$f_i$ 表示第 $i$ 个点期望经过次数：

$$f_i=\begin{cases}f_1=\sum_{(i,j)\in E,j\neq n} \frac{f_j}{deg_j}+1 & i=1\\f_i=\sum_{(i,j)\in E,j\neq n} \frac{f_j}{deg_j} & 1<i<n\end{cases}$$

由于 $n$ 点时就停止游走了，因此不能考虑 $n$ 点的贡献。接下来我们对 $n-1$ 个 $f_i$ 进行高斯消元求解。

我们设 $g_i$ 表示第 $i$ 条边期望经过次数：

$$g_i=\frac{f_u}{d_u}+\frac{f_v}{d_v}\quad E_i=(u,v),u\neq n, v\neq n$$

排序贪心，期望越大的边标号越小。

时间复杂度：$O(n^3)$

---

Code

#include <cstdio>
#include <cmath>
#include <algorithm>

const int N=505,M=5e5+5;
int n,m,tot,lnk[N],ter[M],nxt[M],st[M],ed[M],deg[N];
double a[N][N],b[N],x[N],f[M];

void add(int u,int v) {
	ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
void Gauss(int n) {
	for(int i=1;i<=n;++i) {
		int p=i;
		for(int k=i+1;k<=n;++k) if(fabs(a[k][i])>fabs(a[p][i])) p=k;
		if(i!=p) std::swap(a[i],a[p]),std::swap(b[i],b[p]);
		for(int k=i+1;k<=n;++k) {
			double d=a[k][i]/a[i][i];
			b[k]-=d*b[i];
			for(int j=i;j<=n;++j) a[k][j]-=d*a[i][j];
		}
	}
	for(int i=n;i>=1;--i) {
		for(int j=i+1;j<=n;++j) b[i]-=x[j]*a[i][j];
		x[i]=b[i]/a[i][i];
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		scanf("%d%d",&st[i],&ed[i]);
		add(st[i],ed[i]),add(ed[i],st[i]);
		++deg[st[i]],++deg[ed[i]];
	}
	for(int u=1;u<n;++u) {
		a[u][u]=1.0;
		for(int i=lnk[u];i;i=nxt[i]) {
			int v=ter[i];
			if(v!=n) a[u][v]=-1.0/deg[v];
		}
	}
	b[1]=1;
	Gauss(n-1);
	for(int i=1;i<=m;++i) {
		int a=st[i],b=ed[i];
		if(a!=n) f[i]+=x[a]/deg[a];
		if(b!=n) f[i]+=x[b]/deg[b];
	}
	std::sort(f+1,f+m+1);
	double ans=0;
	for(int i=1;i<=m;++i) ans+=(m-i+1)*f[i];
	printf("%.3lf\n",ans);
}

E42 概率DP 求期望 高斯消元

#include <bits/stdc++.h>
using namespace std;
const int N=510, M=1110000;
const double eps=1e-8;
struct edge{int x,y,pre;}e[M];int elen,last[N];
void add(int x,int y){elen++;e[elen]={x,y,last[x]};last[x]=elen;}
int n,m,d[N],X[M],Y[M];
double a[N][N],f[N],g[M];
void gauss()
{
    for(int i=1;i<n;i++)//第i主元 
    {
        for(int k=i;k<n;k++)if(fabs(a[k][i])>eps) {swap(a[k],a[i]);break;}//换非0行
        for(int k=1;k<n;k++)if(k!=i)//对角化
        {
            double bs=a[k][i]/a[i][i];//第k行的系数是第i行的倍数 
            for(int j=1;j<=n;j++)a[k][j]-=bs*a[i][j];
        }
    }
    for(int i=1;i<n;i++) f[i]=a[i][n]/a[i][i];//除以主元
}
int main()
{
    scanf("%d%d", &n, &m);
    elen=0;memset(last,0,sizeof last);
    memset(d,0,sizeof d);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d", &X[i], &Y[i]);
        add(X[i],Y[i]);add(Y[i],X[i]);
        d[X[i]]++;d[Y[i]]++;
    }
    memset(a,0,sizeof a);memset(f,0,sizeof f);
    for(int x=1;x<n;x++)//构造增广矩阵
    {
        for(int k=last[x];k;k=e[k].pre)
        {
            int y=e[k].y;
            if(y!=n)a[x][y]=-1.0/d[y]; 
        }
        a[x][x]=1;
    }
    a[1][n]=1;
    gauss();//点的期望次数
    for(int i=1;i<=m;i++)g[i]=f[X[i]]/d[X[i]]+f[Y[i]]/d[Y[i]];//边的期望次数
    sort(g+1,g+m+1);
    double ans=0;
    for(int i=1;i<=m;i++) ans+=g[i]*(m-i+1);
    printf("%.3lf",ans);
    return 0;
}