bzoj 3143 游走

#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <functional>

using namespace std;

#define MAXN 511
#define MAXM 250011

typedef pair<int, int> pii;

const double eps = 1e-8;

struct GRAPH {
    vector<vector<int> > s;

    void ClearEdges() {
        for (auto& i : s) {
            i.resize(0);
        }
    }
    void Init(int n) {
        ClearEdges();
        s.resize(n + 1);
    }
    void AddUndi(int u, int v) {
        s[u].push_back(v);
        s[v].push_back(u);
    }
};

struct MATRIX {
    vector<vector<double> > s;

    MATRIX() {}
    MATRIX(size_t a, size_t b) {
        resize(a, b);
    }
    inline size_t row() const {
        return s.size();
    }
    inline size_t col() const {
        return s.at(0).size();
    }
    void resize(size_t a, size_t b) {
        s.resize(a);
        for (size_t i = 0; i < a; ++i)
            s[i].resize(b);
    }
    void clear() {
        for (auto& i : s)
            for (auto& j : i)
                j = 0;
    }
    void swap_row(size_t i, size_t j, size_t k = 0) {
        for (; k < col(); ++k)
            swap(s[i][k], s[j][k]);
    }
    //s[i] -= s[j] * d
    void sub_row(size_t i, size_t j, double d, size_t k = 0) {
        for (; k < col(); ++k)
            s[i][k] -= d * s[j][k];
    }
    //O(n^3)
    void ToUpper(MATRIX& b) {
        for (size_t i = 0; i < row(); ++i) {
            double maxv = fabs(s[i][i]);
            size_t mr = i;
            for (size_t j = i + 1; j < row(); ++j) {
                if (maxv < fabs(s[j][i])) {
                    maxv = fabs(s[j][i]);
                    mr = j;
                }
            }
            swap_row(i, mr, i);
            b.swap_row(i, mr);
            if (maxv < eps) continue;
            for (size_t j = i + 1; j < row(); ++j) {
                double d = s[j][i] / s[i][i];
                sub_row(j, i, d, i);
                b.sub_row(j, i, d);
            }
        }
    }
};

//ax = b
MATRIX solve_destory(MATRIX& a, MATRIX& b) {
    a.ToUpper(b);
    for (int i = a.row() - 1; i; --i) {
        assert(fabs(a.s[i][i]) > eps);
        b.s[i][0] /= a.s[i][i];
        for (int j = 0; j < i; ++j) {
            b.s[j][0] -= b.s[i][0] * a.s[j][i];
        }
    }
    return b;
}

int main() {
    GRAPH g;
    static pii es[MAXM];
    static double gs[MAXN];

    int n, m;
    scanf("%d%d", &n, &m);
    g.Init(n);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &es[i].first, &es[i].second);
        --es[i].first;
        --es[i].second;
    }
    for (int i = 0; i < m; ++i) {
        g.AddUndi(es[i].first, es[i].second);
    }

    MATRIX b(n, 1);
    b.clear();
    b.s[0][0] = 1;
    MATRIX a(n, n);
    for (int i = 0; i < n; ++i) {
        a.s[i][i] = 1;
        for (int v : g.s[i]) {
            if (v != n-1)
                a.s[i][v] = -1.0 / g.s[v].size();
        }
    }
    b = solve_destory(a, b);

    b.s[n-1][0] = 0;
    for (int i = 0; i < m; ++i) {
        gs[i] = b.s[es[i].first][0] / g.s[es[i].first].size() + b.s[es[i].second][0] / g.s[es[i].second].size();
    }
    sort(gs, gs + m, greater<double>());
    double ans = 0;
    for (int i = 0; i < m; ++i) {
        ans += gs[i] * (i + 1);
    }
    printf("%.3f\n", ans);

    return 0;
}