洛谷P3232 [HNOI2013] 游走题解

题目链接：P3232 [HNOI2013] 游走

题意：

给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。

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

输入格式：

第一行是两个整数，分别表示该图的顶点数 $n$ 和边数 $m$。

接下来 $m$ 行每行两个整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。

输出格式：

输出一行一个实数表示答案，保留三位小数。

数据范围：

保证 $2\leq n \leq 500$， $1 \leq m \leq 125000$，$1 \leq u, v \leq n$

给出的图无重边和自环，且从 $1$ 出发可以到达所有的节点。

这种题的套路通常是考虑每个点的 dp 值。

本题中显然可以贪心地为经过次数多的边，标较小的编号。

在平凡的无向图中，经过次数显然与这条边两个端点的度数有关

设 $d_i$ 为每个点的度数，即 $f_i$ 为点 $i$ 的期望经过次数，则

$f_i= \begin{cases} \sum_{(i, j) \in E, j \neq n} \dfrac{f_j}{d_j}+1 & i=1 \\[8pt] \sum_{(i, j) \in E, j \neq n} \dfrac{f_j}{d_j} & 1<i<n \\[8pt] 0 & i = n \end{cases}$

（~~好难看的 dp 式子啊~~）可以发现我们能得到的似乎只有这么多了。

但是有趣的是，这道题 $n \le 500$ ，意味着我们可以直接高斯消元解出 $f_i$ 。

时间复杂度 $\mathcal{O}(n^3)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(515))
#define M ((int)(5e5 + 15))

int pos = 1,head[N],in[N];
struct Edge { int u,v,next; } e[M];
double a[N][N],b[N],x[N],f[M];
void addEdge(int u, int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Gauss(int n)
{
    for(int i = 1; i <= n; i++)
    {
        int p = i;
        for(int k = i + 1; k <= n; k++) if(fabs(a[k][i]) > fabs(a[p][i])) p = k;
        if(i != p) { swap(a[i], a[p]), swap(b[i], b[p]); }
        for(int k = i + 1; k <= n; k++)
        {
            double d = a[k][i] / a[i][i];
            b[k] -= d * b[i];
            for(int j = i; j <= n; j++) a[k][j] -= d * a[i][j];
        }
    }
    for(int i = n; i; i--)
    {
        for(int j = i + 1; j <= n; j++) b[i] -= x[j] * a[i][j];
        x[i] = b[i] / a[i][i];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,m; cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v; ++in[v]; ++in[u];
        addEdge(u,v); addEdge(v,u);
    }
    for(int u = 1; u < n; u++)
    {
        a[u][u] = 1;
        for(int i = head[u], v; i; i = e[i].next)
            if((v = e[i].v) != n) a[u][v] = -1.0 / in[v];
    }
    b[1] = 1; Gauss(n - 1);
    for(int i = 2; i <= pos; i += 2)
    {
        int u = e[i].u, v = e[i].v;
        if(u != n) f[i / 2] += x[u] / in[u];
        if(v != n) f[i / 2] += x[v] / in[v];
    }
    sort(f + 1, f + 1 + m); double res = 0;
    for(int i = 1; i <= m; i++) res += (m - i + 1) * f[i];
    cout << fixed << setprecision(3) << res << '\n';
    return 0;
}