bzoj3143游走

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

要用高斯消元做。
定义f[i]为期望的到点i的次数&＃xff0c;du[i]为点i的度数。那么有
f[i]&＃61;∑j与i相邻,j≠nf[j]du[j]&＃43;[i&＃61;&＃61;1]f[i] &＃61; \sum_{j与i相邻, j\neq n} \frac{f[j]}{du[j]} &＃43; [i&＃61;&＃61;1]f[i]&＃61;j与i相邻,j​&＃61;n∑​du[j]f[j]​&＃43;[i&＃61;&＃61;1]
注意点n只进不出&＃xff0c;所以它对其他点的到达次数没有贡献。
点1一开始就有一次到达。

我们现在有了n个n元一次方程。由于这个方程不规则&＃xff0c;所以我们只能用数值解法来解这个方程。这里采用高斯消元法。

把f解出来后&＃xff0c;就把走每条边的期望次数g[e]求出来。
g[e]&＃61;f[e.u]du[e.u]&＃43;f[e.v]du[e.v]g[e] &＃61; \frac{f[e.u]}{du[e.u]} &＃43; \frac{f[e.v]}{du[e.v]}g[e]&＃61;du[e.u]f[e.u]​&＃43;du[e.v]f[e.v]​

然后从大到小排个序&＃xff0c;从1到m标号即可。

代码&＃xff1a;

#include
#include
#include
#include
#include
#include using namespace std;#define MAXN 511
#define MAXM 250011typedef pair<int, int> pii;const double eps &＃61; 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 &＃43; 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 &＃61; 0; i < a; &＃43;&＃43;i)s[i].resize(b);}void clear() {for (auto& i : s)for (auto& j : i)j &＃61; 0;}void swap_row(size_t i, size_t j, size_t k &＃61; 0) {for (; k < col(); &＃43;&＃43;k)swap(s[i][k], s[j][k]);}//s[i] -&＃61; s[j] * dvoid sub_row(size_t i, size_t j, double d, size_t k &＃61; 0) {for (; k < col(); &＃43;&＃43;k)s[i][k] -&＃61; d * s[j][k];}//O(n^3)void ToUpper(MATRIX& b) {for (size_t i &＃61; 0; i < row(); &＃43;&＃43;i) {double maxv &＃61; fabs(s[i][i]);size_t mr &＃61; i;for (size_t j &＃61; i &＃43; 1; j < row(); &＃43;&＃43;j) {if (maxv < fabs(s[j][i])) {maxv &＃61; fabs(s[j][i]);mr &＃61; j;}}swap_row(i, mr, i);b.swap_row(i, mr);if (maxv < eps) continue;for (size_t j &＃61; i &＃43; 1; j < row(); &＃43;&＃43;j) {double d &＃61; s[j][i] / s[i][i];sub_row(j, i, d, i);b.sub_row(j, i, d);}}}
};//ax &＃61; b
MATRIX solve_destory(MATRIX& a, MATRIX& b) {a.ToUpper(b);for (int i &＃61; a.row() - 1; i; --i) {assert(fabs(a.s[i][i]) > eps);b.s[i][0] /&＃61; a.s[i][i];for (int j &＃61; 0; j < i; &＃43;&＃43;j) {b.s[j][0] -&＃61; 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 &＃61; 0; i < m; &＃43;&＃43;i) {scanf("%d%d", &es[i].first, &es[i].second);--es[i].first;--es[i].second;}for (int i &＃61; 0; i < m; &＃43;&＃43;i) {g.AddUndi(es[i].first, es[i].second);}MATRIX b(n, 1);b.clear();b.s[0][0] &＃61; 1;MATRIX a(n, n);for (int i &＃61; 0; i < n; &＃43;&＃43;i) {a.s[i][i] &＃61; 1;for (int v : g.s[i]) {if (v !&＃61; n-1)a.s[i][v] &＃61; -1.0 / g.s[v].size();}}b &＃61; solve_destory(a, b);b.s[n-1][0] &＃61; 0;for (int i &＃61; 0; i < m; &＃43;&＃43;i) {gs[i] &＃61; b.s[es[i].first][0] / g.s[es[i].first].size() &＃43; b.s[es[i].second][0] / g.s[es[i].second].size();}sort(gs, gs &＃43; m, greater<double>());double ans &＃61; 0;for (int i &＃61; 0; i < m; &＃43;&＃43;i) {ans &＃43;&＃61; gs[i] * (i &＃43; 1);}printf("%.3f\n", ans);return 0;
}