松江品划网站建设维护,住建部网站查询系统,百度免费建立网站,手机制作表格教程原题#xff1a;
link#xff0c;点击这里喵。
题意#xff1a;
给定一个 nnn 个点 mmm 条边的无向连通图#xff0c;图无重边和自环#xff0c;顶点从 111 编号到 nnn#xff0c;边从 111 编号到 mmm。
小 Z 在该图上进行随机游走#xff0c;初始时小 Z 在 111 号顶…原题
link点击这里喵。
题意
给定一个 nnn 个点 mmm 条边的无向连通图图无重边和自环顶点从 111 编号到 nnn边从 111 编号到 mmm。
小 Z 在该图上进行随机游走初始时小 Z 在 111 号顶点每一步小 Z 以相等的概率随机选择当前顶点的某条边沿着这条边走到下一个顶点获得等于这条边的编号的分数。当小 Z 到达 nnn 号顶点时游走结束总分为所有获得的分数之和。 现在请你对这 mmm 条边进行编号使得小 Z 获得的总分的期望值最小。
n≤500n \le 500n≤500。
解法
这种乱动就很烦考虑通过列出方程式解答。
设 fif_ifi 为第个 iii 点期望到达的次数我们有 fu(∑v∈outuv≠nfvdv)[u1]f_u(\sum_{v\in out_u \ v\ne n} \frac{f_v}{d_v} )[u1] fu(v∈outuvn∑dvfv)[u1] 高斯消元即可。
然后就见了。
代码 time ~
#include bits/stdc.h
using namespace std;#define inf 0x3f3f3f3f
typedef long long lnt;namespace DEFINES {
// #define TEST
// #define Debug
#ifdef Debug
#define dprintf(a, ...) printf(a, ##__VA_ARGS__)
#else
#define dprintf(a, ...)
#endif
} // namespace DEFINESstruct my_stream {int x;operator int() {scanf(%d, x);return x;}
} __rp_read;
#define input() __rp_readconst int N 300 20;double v[N][N]; // data of equations// 约定
// x 从 1 开始编号
// v[i][n 1] 存储常数项vectorint G[N];
int n, m, d[N];
double inv_d[N];struct Edge {int x, y;
} edge[N * N];void init_equations() { //v[1][n 1] 1; // 哇嗷for (int i 1; i n; i) { // 注意是 号不能从 n 点获得转移inv_d[i] 1.0 / d[i];}for (int i 1; i n; i) { //v[i][i] -1;for (const int e : G[i]) {v[i][e] inv_d[e];}}
}void sc() {putchar(10);for (int i 1; i n; i) {for (int k 1; k n 1; k) {printf(%8.3lf, v[i][k]);}putchar(10);}putchar(10);
}void solve() { //for (int i 1; i n - 1; i) { // 这一项包有值的省去一步for (int e i 1; e n; e) {double r v[e][i] / v[i][i];for (int k i; k n 1; k) {v[e][k] - r * v[i][k];}}// sc();}// sc();for (int i 1; i n; i) v[i][n 1] * -1;for (int i n; i 1; --i) {v[i][n 1] / v[i][i];v[i][i] 1;for (int e i - 1; e 1; --e) {v[e][n 1] - v[e][i] * v[i][n 1];v[e][i] 0;}}
}double _edge[N * N], _v[N];int main() { //n input(), m input();for (int i 0; i m; i) {int x input(), y input();edge[i] {x, y};d[x], d[y];G[x].push_back(y);G[y].push_back(x);}init_equations();// sc();solve();// sc();for (int i 1; i n; i) { // 是 _v[i] v[i][n 1] / d[i];dprintf(%.3lf\n,_v[i]);}for (int i 0; i m; i) {_edge[i] _v[edge[i].x] _v[edge[i].y];}sort(_edge, _edge m, greaterdouble());double ans 0;for (int i 0; i m; i) {ans _edge[i] * (i 1);dprintf(%.3lf\n,_edge[i]);}printf(%.3lf,ans);return 0;
}
