BZOJ3143【HNOI2013】游走 <高斯消元>

Problem

【HNOI2013】游走

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

一个无向连通图，顶点从$1$编号到$N$，边从$1$编号到$M$。
$\mathrm{小Z}$在该图上进行随机游走，初始时$\mathrm{小Z}$在$1$号顶点，每一步$\mathrm{小Z}$以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当$\mathrm{小Z}$到达$N$号顶点时游走结束，总分为所有获得的分数之和。
现在请你对这$M$条边进行编号，使得$\mathrm{小Z}$获得的总分的期望值最小。

Input

第一行是正整数$N$和$M$，分别表示该图的顶点数和边数。
接下来$M$行每行是整数$u,v\;(1\le u,v\le N)$，表示顶点$u$与顶点$v$之间存在一条边。

Output

仅包含一个实数，表示最小的期望值，保留$3$位小数。

Sample Input

3 3
2 3
1 2
1 3

Sample Output

3.333

Explanation

边$(1,2)$编号为$1$，边$(1,3)$编号$2$，边$(2,3)$编号为$3$。

HINT

$2\le N\le500$
保证图为无向简单连通图

标签：高斯消元

Solution

大致思路是求出每条边的期望经过次数，然后贪心选择边权。
然而对于边来说，并不好确定其期望经过次数，而点的期望经过次数则更好求。

设$x_i$为到达点$i$并继续向下一个点移动的期望次数。那么对于普通的点（非起点$1$或终点$n$），其只能从与其相邻的点走过来，于是对于点$i$，从$i$连出去的点的集合为$S_i$，那么$x_i=\sum_{j\in S_i}\frac{x_j}{d_j}$，其中$d$为点的度数。而对于$1$号点，初始时一定在$1$号点上，因此一定初始就有$1$次的经过次数，而游走过程中的情况与普通点相同，于是$x_1=\sum_{j\in S_1}\frac{x_j}{d_j}$。对于$n$号点，由于到了$n$后不能继续走动，即只进不出，于是一定不会经过（因为前面经过的定义是要有向下一个点移动的可能），因此$x_n=0$。
于是有方程组

$$\begin{cases} x_1=1+\sum_{i\in S_1}\frac{x_i}{d_i}\\ x_2=\sum_{i\in S_2}\frac{x_i}{d_i}\\ x_3=\sum_{i\in S_3}\frac{x_i}{d_i}\\ \;\;\;\;\vdots\;\;\;\;\;\;\vdots\\ x_{n-1}=\sum_{i\in S_{n-1}}\frac{x_i}{d_i}\\ x_n=0\\ \end{cases}$$

用高斯消元可以解得$\lbrace x\rbrace$。

对于一条边$i$，其端点为$u$和$v$，要经过$i$必定只能是从$u$到$v$或从$v$到$u$。在$u$时有$\frac{1}{d_u}$的概率走这条边，在$v$时有$\frac{1}{d_v}$的概率走这条边，于是第$i$条边的期望经过次数为$y_i=\frac{x_u}{d_u}+\frac{x_v}{d_v}$。
求出$\lbrace y\rbrace$后从大到小排序，贪心使得期望经过次数越大的边权越小，即可得到最小的期望路径长度。

Code

#include <bits/stdc++.h>
#define EPS 1e-7
#define MAX_N 500
#define MAX_M 250000
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, u[MAX_M+5], v[MAX_M+5], d[MAX_N+5];
dnt f[MAX_N+5][MAX_N+5], x[MAX_N+5], y[MAX_M+5];
void Gauss() {
    for (int i = 1, t; i <= n; i++) {
        for (t = i; t <= n; t++) if (fabs(f[i][t]) >= EPS) break;
        if (t > n) continue; swap(f[i], f[t]);
        for (int j = 1; j <= n; j++) if (i^j) {
            dnt div = f[j][i]/f[i][i];
            for (int k = 1; k <= n+1; k++)
                f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++) x[i] = f[i][n+1]/f[i][i];
}
int main() {
    read(n), read(m); dnt ans = 0;
    for (int i = 1; i <= m; i++)
        read(u[i]), read(v[i]), d[u[i]]++, d[v[i]]++;
    for (int i = 1; i <= m; i++)
        f[u[i]][v[i]] -= 1.0/d[v[i]], 
        f[v[i]][u[i]] -= 1.0/d[u[i]];
    for (int i = 1; i <= n; i++) f[n][i] = 0;
    for (int i = 1; i <= n; i++) f[i][i] = 1;
    f[1][n+1] = 1, Gauss();
    for (int i = 1; i <= m; i++) y[i] = x[u[i]]/d[u[i]]+x[v[i]]/d[v[i]];
    sort(y+1, y+m+1); for (int i = 1; i <= m; i++) ans += y[i]*(m-i+1);
    return printf("%.3lf\n", ans), 0;
}