题意
一个无向简单连通图，边权为 $1\dots m$ 的整数。问分配边权后，从点 1 随机游走到点 $n$ 的最小期望距离。
思路
刚看完《训练指南》上面的矩阵一部分，做一做相关省选题练练手，结果第一题就不会做……
这是最开始的错误思路：
我们对每个点显然可以列出递推式，设 $a_u$ 为点 1 走到点 $u$ 的期望距离。那么一定有：
\[a_u = \sum_{<u, v> \in \mathbb{E}} \frac{1}{\deg{u}}(a_v+w_{<u, v>})\]为什么？我们考虑是从哪个点 $v_i$ 沿着边 $<v_i, u>$ 走到 $u$ 的。对于沿着每一条边 $<v_i, u>$ 走到 $u$ 点的情况，由全期望公式知，对应的期望值为 $a_{v_i} + w_{<v_i, u>}$ . 所有情况加权平均即为上式。
但是我们并不知道每条边的长度啊？！这样就不能做了……
我们换个思路：不妨写出每个点期望经过的次数 $b_u$ ，则
\[b_u = \sum_{<u, v> \in \mathbb{E}}\frac{b_v}{\deg v}\]为什么是除以 $\deg v$ 呢？不要忘了，每个点的期望经过次数等于 邻接弧 期望经过次数之和。而对于每条和 $u$ 邻接的弧 $<u, v>$ ，经过它到 $u$ 的次数都是 $b_v / \deg v$ ，因为到达邻接点 $v$ 的期望次数为 $b_v$ ，而又有 $ 1 / \deg v$ 的概率经过弧 $<v, u>$ ，根据期望定义和全期望公式，可得上式。
我们再来考虑不限定经过方向的前提下，每条弧的期望经过次数 $c_{<u, v>}$。显然有：
\[c_{<u, v>} = \frac{b_u}{\deg_u} + \frac{b_v}{\deg_v}\]则答案为
\[ans = \sum_{<u, v> \in \mathbb{E}} c_{<u, v>} w_{<u, v>}\]等等…… $\sum_i a_i b_i$ 求最值？这不就是排序不等式么……
先高斯消元求 ${b_n}$ ，再利用逆序和最小安排权值即可。由于是无向连通图，一定有解。
这个题目中，我学到了几点：
- 一定要灵活利用好期望的线性、全期望公式，更别忘了期望的定义式。
- 点和边的对偶转化是很方便的。如果要求边相关期望，而点的期望更好求（一般都是这样），可以进行转化。
- 最优化问题有时候可以用不等式解决。
代码
注意实现的一些细节，调了好久没调出来，看了Sengxian的题解才知道：
- 对于点 1 ，不能漏掉最开始的一次经过，也就是经过次数的期望要加上 1 。按照《训练指南》的说法，可以看成从虚拟的节点 0 以 1 的概率转移而来。
- 对于点 $n$ ，由于到了它就不再继续游走，比较特殊，我们不对它列方程解期望；对于一端是 $n$ 的弧，我们只考虑向 $n$ 的方向走的期望次数。
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
const int MAXN = 1000;
const double eps = 1e-8;
struct Edge { int v, next; };
int n, m, e_ptr = 1, deg[MAXN+10], head[MAXN+10]; Edge E[(MAXN*MAXN+10)<<1];
double b[MAXN+10][MAXN+10], c[(MAXN*MAXN+10)<<1];
vector<pair<int, int> > E0;
inline int dcmp(double x) {
return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}
void AddEdge(int u, int v) {
E[++e_ptr] = (Edge) { v, head[u] }; head[u] = e_ptr;
}
void AddPair(int u, int v) {
AddEdge(u, v); AddEdge(v, u);
deg[u]++; deg[v]++;
E0.push_back(make_pair(u, v));
}
void Init() {
int u, v;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
AddPair(u, v);
}
}
void Gauss(int n, double A[MAXN+10][MAXN+10]) {
for(int i = 1; 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(r != i)
for(int j = 1; j <= n+1; j++)
swap(A[i][j], A[r][j]);
for(int k = i+1; k <= n; k++) {
double t = A[k][i] / A[i][i];
for(int j = 1; j <= n+1; j++)
A[k][j] -= t * A[i][j];
}
}
for(int i = n; i >= 1; i--) {
for(int j = i+1; j <= n; j++)
A[i][n+1] -= A[i][j] * A[j][n+1];
A[i][n+1] /= A[i][i];
}
}
void Work() {
double ans = 0;
for(int u = 1; u <= n-1; u++) {
b[u][u] = 1;
for(int j=head[u]; j; j=E[j].next) {
int v = E[j].v;
if(v == n) continue;
b[u][v] = (-1.0) / deg[v];
}
b[u][n] = bool(u == 1);
}
Gauss(n-1, b); // n-1个方程， n-1个变量
for(int i = 0; i < m; i++) {
pair<int, int> &e = E0[i];
double p = (e.fst != n ? b[e.fst][n] / deg[e.fst] : 0.0);
double q = (e.snd != n ? b[e.snd][n] / deg[e.snd] : 0.0);
c[i] = p + q;
}
sort(c, c + m);
for(int i = 0; i < m; i++)
ans += c[i] * (m-i);
printf("%.3lf", ans);
}
int main() {
Init(); Work();
return 0;
}
