#C241017B. [HNOI2013] 游走

标签（Label）

• 数学推理
• 高斯消元
• 数学
• 动态规划
• 期望

网址（Website）

「HNOI2013」游走 - Super

P3232 [HNOI2013] 游走

题解（Solution）

是一种神奇的方式。

令 $f_i$ 表示当前经过点 $i$ 的期望，可以得：
$$
\begin{cases}
f_1 = \sum_{y\in E}\frac{f_y}{d_y}+1\\
f_x = \sum_{y\in E}\frac{f_y}{d_y},\qquad x\in[2,n-1]\\
f_n = 0
\end{cases}
$$
其中 $E$ 表示当前点 $x$ 通往的点的点集 $y$ ，结点 $1$ 最开始就要走一次，结点 $n$ 不能走，因此经过期望为 $0$ 。

然后推对于边的期望，对于第 $i$ 条边，$g_i=\frac{f_x}{d_x}+\frac{f_y}{d_y}$ ，很明显，对于期望大的点我们需要让其边权最小，排序后赋编号即可。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define eps 1e-9
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2005;
const int M = 1012345;
bool ST;

vector<int> ft[N];
int n,m;
double ans;

double a[N][N], f[N];
void Gaosi(int n){//默认第n+1项为0 
	For(i,1,n){
		int mx = i;
		For(j,i+1,n) mx = fabs(a[mx][i]) > fabs(a[j][i]) ? mx : j;
		For(j,1,n+1) swap(a[i][j], a[mx][j]);
		assert(fabs(a[i][i]) > eps);
		
		Rof(j,n+1,1) a[i][j] /= a[i][i];
		For(j,1,n) if(j!=i){
			double beishu = a[j][i]/a[i][i];
			For(k,1,n+1) a[j][k] -= beishu*a[i][k];
		}
	}For(i,1,n) f[i] = a[i][n+1];
}

int st[M],ed[M];
double g[M],d[N];
void solve(){
	n = rd(), m = rd();
	For(i,1,m){
		int x = st[i] = rd(), y = ed[i] = rd();
		ft[x].emplace_back(y); 
		ft[y].emplace_back(x); 
		d[x]++, d[y]++;
	}
	
	a[1][n] = 1.;//点1有常数项 
	For(x,1,n-1){
		a[x][x] = 1.;
		for(auto y:ft[x]){
			if(y==n) continue;
			a[x][y] -= 1./d[y];
		}
	}
	Gaosi(n-1);
	For(i,1,m){
		int x = st[i], y = ed[i];
		g[i] = f[x]/d[x] + f[y]/d[y];
	}
	sort(g+1,g+m+1,greater<double>());//从da到xiao排序
	For(i,1,m) ans += 1.*g[i]*i;
	printf("%.3lf\n",ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}