BZOJ 3143 - [Hnoi2013]游走

#数学 #高斯消元 #贪心 #数学期望

Published on 2016-11-26

描述

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

分析

根据期望的线性，获得的总分的期望值等于每条边的期望经过次数经过次数乘上这条边的编号。由于每条边的期望经过次数与边如何标号是无关的，所以我们求出每条边的期望经过次数，然后贪心地给边标号：按照期望次数从大到小排序，依次标号，这样一定能让总分的期望最小。

发现求经过边的期望并不是很好求，而且边是 $O(n^2)$ 级别的，我们转而考虑求点的期望，从点的期望算出边的期望。设 $e_i$ 为经过点 $i$ 的期望次数， $d_i$ 为点 $i$ 的度，从而边 $(u, v), u\le v$ 的期望经过次数就是 $e_u \cdot \frac 1 {d_u} + e_v \cdot \frac 1 {d_v}$ （如果 $v = n$ ，那么就是 $e_u \cdot \frac 1 {d_u}$ ）。
考虑如何求 $e_i$ ，由于这并不是一个拓扑图，所以无法递推，只能考虑用高斯消元解线性方程组，这一思想在 [Jsoi2009]有趣的游戏出现过，我们还是先列出方程（设 $p_{i, j}$ 为从 $j$ 走到 $i$ 的概率）：
对于 1 号点，一开始就经过了一次，所以：

e_1 = 1 + p_{1, 1}e_1 + p_{1, 2}e_2 + \cdots + p_{i, n}e_n

对于其他点：

e_i = p_{i, 1}e_1 + p_{i, 2}e_2 + \cdots + p_{i, n}e_n

移项后就变成了：

我们考虑求 $p_{i, j}$ ：如果有边 $j\rightarrow i$ ，那么对 $P_{i, j}$ 的贡献就是 $\frac 1 {d_j}$ 。由于到 $n$ 点就停止了，所以我们不考虑从 $n$ 出发的所有边。
高斯消元解方程，之后贪心即可。复杂度： $O(n^3 + m\log n)$ ，注意边会达到 $\frac {n(n - 1)} 2$ ，数组不要开小了。

总结：利用好期望的线性性质，可以大大的简化问题。

代码

//  Created by Sengxian on 2016/11/26.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3143 期望 + 高斯消元
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 500 + 3;
vector<int> G[MAX_N];
int n, m;

double a[MAX_N][MAX_N], e[MAX_N], eE[MAX_N * MAX_N];

void gauss_jordan(int n, double a[MAX_N][MAX_N]) {
    for (int i = 0; i < n; ++i) {
        int idx = i;
        for (int j = i + 1; j < n; ++j)
            if (fabs(a[j][i]) > fabs(a[idx][i])) idx = j;
        assert(fabs(a[idx][i]) > 1e-10);
        if (idx != i) for (int j = i; j <= n; ++j) swap(a[i][j], a[idx][j]);
        for (int j = 0; j < n; ++j) if (i != j) {
            double t = a[j][i] / a[i][i];
            for (int k = i; k <= n; ++k) a[j][k] -= a[i][k] * t;
        }
    }
}

void build() {
    for (int i = 0; i < n; ++i) a[i][i] = -1;
    a[0][n] = -1;
    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < (int)G[i].size(); ++j)
            a[G[i][j]][i] += 1.0 / ((int)G[i].size());
}

pair<int, int> edges[MAX_N * MAX_N];
int main() {
    n = readInt(), m = readInt();
    for (int i = 0, u, v; i < m; ++i) {
        u = readInt() - 1, v = readInt() - 1;
        if (u > v) swap(u, v);
        edges[i] = make_pair(u, v);
        G[u].push_back(v), G[v].push_back(u);
    }
    build();
    gauss_jordan(n, a);
    for (int i = 0; i < n; ++i) e[i] = a[i][n] / a[i][i];
    for (int i = 0; i < m; ++i) {
        eE[i] += e[edges[i].first] / G[edges[i].first].size();
        if (edges[i].second != n - 1) eE[i] += e[edges[i].second] / G[edges[i].second].size();
    }
    sort(eE, eE + m);
    double ans = 0;
    for (int i = m - 1; i >= 0; --i) ans += eE[i] * (m - i);
    printf("%.3f\n", ans);
    return 0;
}

BZOJ 4008 - [HNOI2015]亚瑟王 NOIP 2016 Day 2 题解

Sengxian's Blog

BZOJ 3143 - [Hnoi2013]游走

描述

分析

代码