圖上游走

金牌導航 期望-6

題目大意

給出一個無向連通圖，小明初始在點1，每一步等概率地走向相連的其他點，當走到n時結束，定義分數從1為走到n的過程中經過的邊的編號之和，現在讓你給這m條邊重新編號，使最大期望分數最小

輸入樣例

3 3 2 3 1 2 1 3

輸出樣例

3.333

解題思路

一條邊的貢獻=期望經過次數$\times$編號
為了使期望分數最小，讓期望經過次數大的編號小即可
那么如何求邊的期望經過次數呢
對于連接x,y的邊，有：
$s{l}_i=\frac{s_x}{de{g}_x}+\frac{s_y}{de{g}_y}$
其中sl，s分別為邊，點的期望次數，deg為連接的邊數
意思就是：從x的點有$\frac{1}{de{g}_x}$的概率走過這條邊，再乘上$s_x$即為從x點走過該邊的概率（y同理）
求sl的方法已經有了，那么考慮求s
對于s，我們有式子：
$$s_i=\frac{s_1}{de{g}_1}+\frac{s_2}{de{g}_2}...\frac{s_{de{g}_i}}{de{g}_{de{g}_i}}$$
里面的數表示和i相連的數
移項得到
$$0=?s_i+\frac{s_1}{de{g}_1}+\frac{s_2}{de{g}_2}...\frac{s_{de{g}_i}}{de{g}_{de{g}_i}}$$
這樣我們就得到n-1個式子（到n后不會再往回走，所以關于n的式子不要）
注：對于1的式子，有初始的一次，移項后得到的是：
$$?1=?s_i+\frac{s_1}{de{g}_1}+\frac{s_2}{de{g}_2}...\frac{s_{de{g}_i}}{de{g}_{de{g}_i}}$$
對于這n-1個式子，我們高斯消元得到s，然后求結果即可

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 510 using namespace std; int n, m, x, y, tot, maxn, head[N]; double ans, l[2*N*N], deg[N], f[N][N]; struct rec {int to, next; }a[2*N*N]; double abss(double x) {if (x < 0) return -x;return x; } void add(int x, int y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot;a[++tot].to = x;a[tot].next = head[y];head[y] = tot;deg[x] += 1.0;deg[y] += 1.0; } void gaus(int n)//高斯消元 {for (int i = 1; i <= n; ++i){maxn = i;for (int j = i + 1; j <= n; ++j)if (abss(f[j][i]) > abss(f[maxn][i]))maxn = j;for (int j = 1; j <= n + 1; ++j)swap(f[i][j], f[maxn][j]);for (int j = 1; j <= n; ++j)if (i != j)for (int k = i + 1; k <= n + 1; ++k)f[j][k] -= f[i][k] * (f[j][i] / f[i][i]);}for (int i = 1; i <= n; ++i)f[i][n + 1] /= f[i][i];return; } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++i){scanf("%d%d", &x, &y);add(x, y);}for (int i = 1; i < n; ++i){f[i][i] = -1.0;for (int j = head[i]; j; j = a[j].next)if (a[j].to != n)//到n后不走了f[i][a[j].to] = 1.0 / deg[a[j].to];//得出方程}f[1][n] = -1.0;gaus(n - 1);for (int i = 1; i <= m; ++i)l[i] = f[a[i*2].to][n] / deg[a[i*2].to] + f[a[i*2-1].to][n] / deg[a[i*2-1].to];//求出期望sort(l + 1, l + 1 + m);reverse(l + 1, l + 1 + m);//從大到小for (int i = 1; i <= m; ++i)ans += l[i] * i;printf("%.3lf", ans);return 0; }

總結

以上是生活随笔為你收集整理的【期望】【高斯消元】图上游走（金牌导航 期望-6）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。