题解

思路分析

这是一道 概率期望 + 高斯消元 + 贪心 的经典问题。

问题建模

• 从节点1随机游走到节点 $N$
• 每步等概率选择相邻边
• 每条边有编号，经过获得对应分数
• 目标：给边重新编号，使期望总分最小

核心思路

1. 期望计算

设边 $e$ 被经过的期望次数为 $g_e$，边编号为 $id_e$，则：

$$\text{期望总分} = \sum_{e=1}^{M} g_e \cdot id_e$$

2. 高斯消元求期望次数

设 $f_i$ 表示从节点 $i$ 出发到达节点 $N$ 的期望步数。

对于节点 $i$（$i \neq N$）：

$$f_i = 1 + \frac{1}{deg_i} \sum_{j \in adj(i)} f_j$$

其中 $deg_i$ 是节点 $i$ 的度数。

边界条件：$f_N = 0$。

这是一个线性方程组，使用高斯消元求解。

对于每条边 $(u, v)$，其被经过的期望次数为：

$$g_{u,v} = \frac{f_u}{deg_u} + \frac{f_v}{deg_v} \quad (v \neq N) $$

如果 $v = N$：

$$g_{u,N} = \frac{f_u}{deg_u}$$

3. 贪心分配编号

将所有边按期望次数 $g_e$ 升序排序，编号从小到大分配。

这样期望次数大的边分配大编号，使总期望最小。

算法步骤

1. 建图：

   • 读入边，建立邻接表
   • 统计每个节点的度数

2. 高斯消元：

   • 列方程组求 $f_i$
   • 使用高斯消元求解

3. 计算边的期望：

   • 对每条边计算 $g_e$

4. 贪心分配编号：

   • 按 $g_e$ 升序排序
   • 计算期望总分

复杂度分析

• 高斯消元：$O(N^3)$
• 排序：$O(M \log M)$
• 总时间复杂度：$O(N^3 + M \log M)$
• 空间复杂度：$O(N^2 + M)$

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=125010;
int n,m,out[N],u[M],v[M];
vector<int>t[N];
double ans=0,a[N][N],g[M];
void guess(int n){
	for(int i=1;i<=n;i++){
		int maxn=i;
		for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[maxn][i])) maxn=j;
		for(int j=1;j<=n+1;j++) swap(a[maxn][j],a[i][j]);
		for(int j=n+1;j>=i;j--) a[i][j]=a[i][j]/a[i][i];
		for(int j=1;j<=n;j++){
			if(j!=i){
				double temp=a[j][i]/a[i][i];
				for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*temp;
			}
		}
	}
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		if(x==n) swap(x,y);
		u[i]=x,v[i]=y;
		t[x].push_back(y);t[y].push_back(x);
		out[x]++;out[y]++;
	}
	a[1][n]=1.0;
	for(int i=1;i<n;i++){
		a[i][i]=1.0;
		for(int j:t[i]){
			if(j!=n) a[i][j]=-1.0/out[j];
		}
	}
	guess(n-1);
	for(int i=1;i<=m;i++){
		if(v[i]==n) g[i]=a[u[i]][n]*1.0/out[u[i]];
		else g[i]=a[u[i]][n]*1.0/out[u[i]]+a[v[i]][n]*1.0/out[v[i]];
	}
	sort(g+1,g+1+m);
	for(int i=1;i<=m;i++) ans+=g[i]*1.0*(m-i+1);
	cout<<fixed<<setprecision(3)<<ans;
}

题解

记 $f_u$ 为从点 $u$ 出发一直走到 $N$ 号点的过程中所获得分数的期望。对于终点 $f_N = 0$，而对于其它点有

$$f_u = \frac{1}{\deg(u)} \sum_{(u,v)\in E} (w_{uv} + f_v), $$

其中 $w_{uv}$ 是边的编号。由于边的编号未知，我们只需要先求出“期望经过每条边的次数”，把编号大的边放在期望次数小的位置即可。

进一步化简可得线性方程组：把式子移项，得到

$$f_u - \sum_{v\neq N} \frac{1}{\deg(v)} f_v = \begin{cases} 1, & u = 1, \\ 0, & u \neq 1, N. \end{cases} $$

这正好是一个 $(N-1)$ 阶的高斯消元方程，可以解出所有 $f_u$。对于一条边 $(x,y)$，它被经过的期望次数等于从两端出发的转移概率之和，即

$$g_{xy} = \frac{f_x}{\deg(x)} + \frac{f_y}{\deg(y)} $$

（若其中一端是终点，则只有另一端的项）。

把所有边的 $g_i$ 按升序排序之后，依次分配编号 $1..M$，这样对每条边的贡献就是 $g_i \times$ 对应编号。由于我们希望总期望最小，应该把大的编号分给较小的 $g_i$，因此最终答案即为

$$\sum g_i \cdot (M - i + 1).$$

实现时用高斯消元解线性方程，再排序即可输出保留三位小数的期望。

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=125010;
int n,m,out[N],u[M],v[M];
vector<int>t[N];
double ans=0,a[N][N],g[M];
void guess(int n){
	for(int i=1;i<=n;i++){
		int maxn=i;
		for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[maxn][i])) maxn=j;
		for(int j=1;j<=n+1;j++) swap(a[maxn][j],a[i][j]);
		for(int j=n+1;j>=i;j--) a[i][j]=a[i][j]/a[i][i];
		for(int j=1;j<=n;j++){
			if(j!=i){
				double temp=a[j][i]/a[i][i];
				for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*temp;
			}
		}
	}
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		if(x==n) swap(x,y);
		u[i]=x,v[i]=y;
		t[x].push_back(y);t[y].push_back(x);
		out[x]++;out[y]++;
	}
	a[1][n]=1.0;
	for(int i=1;i<n;i++){
		a[i][i]=1.0;
		for(int j:t[i]){
			if(j!=n) a[i][j]=-1.0/out[j];
		}
	}
	guess(n-1);
	for(int i=1;i<=m;i++){
		if(v[i]==n) g[i]=a[u[i]][n]*1.0/out[u[i]];
		else g[i]=a[u[i]][n]*1.0/out[u[i]]+a[v[i]][n]*1.0/out[v[i]];
	}
	sort(g+1,g+1+m);
	for(int i=1;i<=m;i++) ans+=g[i]*1.0*(m-i+1);
	cout<<fixed<<setprecision(3)<<ans;
}