526互联

题解 NOD2207D【电报】

发布时间 2023-06-10 16:33:28作者: caijianhong

前置知识：高斯消元

已知 \(n\) 元线性一次方程组。关于 \(x_1,x_2,\cdots,x_n\)。

\[\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases} \]

求出它的唯一解。或者无解。或者无数解。

考虑写成一个类似矩阵的形式（假设 \(n=3\)）：

\[\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} &|& b_1\\ a_{2,1} & a_{2,2} & a_{2,3} &|& b_2\\ a_{3,1} & a_{3,2} & a_{3,3} &|& b_3 \end{bmatrix}\]

对于这个矩阵我们可以有三种操作，而不改变它的任何信息：

  • 交换任意两行。
  • 对于一行的所有数字乘上同一个不为零的数。
  • 将某一行与另一行对应位置相加，放在另一行，前面的某一行不变。

我们可以用这三种操作解这个矩阵，如果有解。我们的做法是这样的：

  • 选一行的一个未知数。
  • 化其为一。
  • 用它消掉其他行的这个未知数，这样这个矩阵就只剩下它一个了。
  • 重复上述操作 \(n\) 次以至于每一行都形如 \(x_i=b'_i\)。

没有唯一解的情况，就是找完所有行发现有一个未知数完全没有了。

细分无解和无数解请见 https://www.luogu.com.cn/problem/solution/P2455 我不想再写了

problem

\(n\) 个点 \(m\) 条边的无向简单图。每条边应该有一个权值，你要用 \(1\) 到 \(m\) 的数字给它们赋权值，一个数字只能用一次。

一个人在图上，从 1 开始随机游走，每次等概率选择一条边走过去，花费代价是这条边的权值。

请合理地赋权值，使得这个人第一次走到 \(n\) 的期望代价最小。\(n\leq 500\)。

solution 1（\(n\leq 10\)）

假设 \(E[i]\) 为从 \(i\) 第一次走到 \(n\) 的期望代价，可以写成一个关于其他 \(E[j]\) 和边权的多项式。

通过将 \(E[i]\) 当作未知数高斯消元，得到表示 \(E[1]\) 的关于所有边权的多项式。将这个多项式的系数从小到大排序，系数更小的赋予更大的权值，这样就能使 \(E[1]\) 最小。

solution 2

solution 1 的劣势在于边数太多了（\(O(n^2)\)），无法高斯消元。

考虑我们最后算出来那个系数是什么，实际上是那一条边的期望经过次数。而注意到 \((u,v)\) 边的经过次数显然等于 \(\frac{f_u}{deg_u}+\frac{f_v}{deg_v}\)，其中 \(f_i\) 表示这个点的期望经过次数。

考虑计算 \(f_i\)。

  • \(f_n=0\)。
  • \(f_i=\sum_v\frac{f_v}{deg_v}\)
  • 注意 \(f_1\) 一上来就要经过一次，所以是 \(f_1=1+\sum_v\frac{f_v}{deg_v}\)

高斯消元上述内容即可。

code

点击查看代码 
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const double eps=1e-7;
int n,m,deg[510],U[1<<18],V[1<<18];
vector<double> a[510];
void guass(){
	auto dec=[&](int i,int j,double d){for(int k=0;k<=n;k++) a[i][k]-=a[j][k]*d;};
	auto div=[&](int i,double d){for(int k=0;k<=n;k++) a[i][k]/=d;};
	for(int i=0;i<n;i++){
		int r=i; 
		for(int j=i+1;j<n;j++) if(fabs(a[j][i])>fabs(a[r][i])) r=j;
		if(fabs(a[r][i])<eps) assert(0);
		swap(a[i],a[r]);
		for(int j=0;j<n;j++) if(i!=j) dec(j,i,a[j][i]/a[i][i]);
	}
	for(int i=0;i<n;i++) div(i,a[i][i]);
}
int main(){
//	#ifdef LOCAL
//	 	freopen("input.in","r",stdin);
//	#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&U[i],&V[i]),deg[--U[i]]++,deg[--V[i]]++;
	for(int i=0;i<n;i++) a[i]=vector<double>(n+1),a[i][i]=-1;
	for(int i=1;i<=m;i++){
		auto add=[&](int u,int v){if(u!=n-1) a[u][v]+=1.0/deg[v];};
		add(U[i],V[i]),add(V[i],U[i]);
	}
	a[0][n]=-1,a[n-1][n-1]=1;
	guass();
	vector<double> w; w.reserve(m);
	for(int i=1;i<=m;i++) w.push_back(a[U[i]][n]/deg[U[i]]+a[V[i]][n]/deg[V[i]]);
	sort(w.begin(),w.end());
	double ans=0;
	for(int i=0;i<m;i++) ans+=w[i]*(m-i);
	printf("%.10lf\n",ans);
	return 0;
}