P3232 [HNOI2013]游走

传送门

思路

因为边数很多，所以如果我们考虑用边来设立状态的话，会直接爆掉

考虑到期望有线性性，我们将边拆成独立的贡献

对于边 \((u,v)\)，它被经过的期望实际上就是 \(\frac{E_u}{d_u}+\frac{E_v}{d_v}\)（\(E(u)\) 表示点 \(u\) 被经过的期望）

最后的答案就是：每条边被经过的期望\(\times\)它的边权，所以我们设边权的时候可以用贪心（被经过的期望越大，边权越小）

因此我们考虑如何求出点被经过的期望

我们其实有如下转移方程：

\[\begin{aligned} E_1&=\sum_{(1,j)\in Edge\ and\ j \not = n}\frac{E_j}{d_j}+1\\ E_i&=\sum_{(i,j)\in Edge\ and\ j \not = n}\frac{E_j}{d_j}\ (i>1)\\ \end{aligned}\]

\(E_1\) 要加 \(1\) 是因为开始就在 \(1\) 号点，因此 \(100%\) 会经过 \(1\) 先

\(j\not = n\) 是因为到了 \(n\) 就停了，不可能从 \(n\) 转移

这样我们就可以用高斯消元做了

最后吐槽一个点：为什么用结构体排序那么慢啊，不开 \(O_2\) 都过不了......

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
inline int reads()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, m, du[505];
struct Node
{
    int u, v;
}r[125005];
struct gass
{
    double k[505], b;
}l[505]; double f[505];
double ans; std::vector s;
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = reads(), m = reads();
    for(int i = 1; i <= m; i++)
    {
        int u = reads(), v = reads();
        r[i] = (Node){u, v};
        du[u]++, du[v]++;
    }
    for(int i = 1; i <= n; i++)
        l[i].k[i] = 1.0;
    for(int i = 1; i <= m; i++)
    {
        if(r[i].v ^ n) l[r[i].u].k[r[i].v] = -1.0 / du[r[i].v];
        if(r[i].u ^ n) l[r[i].v].k[r[i].u] = -1.0 / du[r[i].u];
    }
    l[1].b = 1;
    for(int i = 1, Mx; i <= n; i++)
    {
        Mx = i;
        for(int j = i; j <= n; j++)
            if(l[j].k[i])
            {
                Mx = j;
                break;
            }
        std::swap(l[i], l[Mx]);
        for(int j = 1; j <= n; j++)
        {
            if(i == j) continue;
            double mul = l[j].k[i] / l[i].k[i];
            for(int k = 1; k <= n; k++)
                l[j].k[k] -= l[i].k[k] * mul;
            l[j].b -= l[i].b * mul;
        }
    }
    for(int i = 1; i <= n; i++) f[i] = l[i].b / l[i].k[i];
    for(int i = 1; i <= m; i++)
    {
        double p = 0;
        if(r[i].u != n) p += f[r[i].u] / du[r[i].u];
        if(r[i].v != n) p += f[r[i].v] / du[r[i].v];
        s.emplace_back(p);
    }
    std::sort(s.begin(), s.end());
    for(int i = 0; i < s.size(); i++)
        ans += s[i] * (m - i);
    printf("%.3lf", ans);
    return 0;
}
luogu题解贪心期望DP高斯消元

相关

算法第四章《贪心策略》上机实践报告

洛谷 P2279 [HNOI2003]消防局的设立 贪心

CF1479B Painting the Array（贪心+DP）

cogs 1440. [NOIP2013]积木大赛 贪心水题

P1850 换教室 期望dp

天天快乐编程集训队2021暑假训练-0802-贪心题解

CF1190E Tokitsukaze and Explosion 二分、贪心、倍增、ST表

贪心学院计算机视觉CV训练营

海盗分金问题SQL求解（贪心算法）

贪心优化

51 Nod 1091 线段的重叠 (贪心算法)

贪心——55. 跳跃游戏 && 45.跳跃游戏II

标签