A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3143 游走 概率dp+高斯消元
发表于: | 分类: Oi | 评论:0 | 阅读:212

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

首先我们虽然求不出一个点的期望的大小,但是我们可以求出从1号点到其他点的概率的大小,设1~i的概率为$p_i$,我们可以得到
$$p_i = \sum\limits_{i\to j}{\frac{p_j}{deg_j}}$$
把所有点$p_i$的式子放在一起,他就变成了一个$n$元一次的方程组
然后直接上高斯消元解出来就行了
但是到现在为止只求出了$p_i$,我们考虑已知两个点的概率分别为$p_1,p_2$,如何表示出过一条边的情况
这个值是$w_{1 \to 2} = \frac{p_1}{deg_1}+\frac{p_2}{deg_2}$
我开始认为是乘法,但是其实并不是,因为只要有一个经过就算经过了这条边

在这样处理之后我们得到了每条边被经过的概率,显然排序之后小概率的对大权值才行,直接算一下就行了,最后的答案就是
$$ans = \sum\limits_{i=1}^{m}{(m-i+1)*w_i}$$

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
typedef long double ld;
const double eps = 1e-13;
const int N = 500+5;
const int M = N*N;
using namespace std;

int head[N];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

ld a[N][N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int deg[N];
ld G[M];

int main()
{
    int n = read(), m = read();
    for(int i=1;i<=m;++i)
    {
        int x = read(),y = read();
        add(x,y); deg[x]++,deg[y] ++;
    }
    --n;a[1][n+1] = -1.0;
    for(int x=1;x<=n;++x)
    {
        a[x][x] = -1.0;
        for(int i=head[x];i;i=edge[i].next)
            if(edge[i].to!=n+1)
                a[x][edge[i].to] = 1.0/deg[edge[i].to];
    }
    for(int i=1;i<=n;++i)
    {
        int tt = i;
        for(int j=i;j<=n;++j)
            if(fabs(a[j][i]) > eps) tt = j;
        for(int j=1;j<=n+1;++j) swap(a[i][j],a[tt][j]);
        for(int j=1;j<=n;++j)
            if(j!=i && fabs(a[j][i]) > eps)
            {
                ld t = a[j][i] / a[i][i];
                for(int k=1;k<=n+1;++k)
                    a[j][k] -= a[i][k] * t;
            }
    }
    for(int i=1;i<=n;++i) a[i][i] = a[i][n+1] / a[i][i];
    for(int i=2;edge[i].to;i+=2)
    {
        int tt1 = edge[i].to,tt2 = edge[i^1].to;
        G[i>>1]  = a[tt1][tt1]/deg[tt1] + a[tt2][tt2]/deg[tt2];
    }
    sort(G+1,G+m+1);
    ld ans = 0;
    for(int i=1,val=m;i<=m;++i,val--) ans += (ld)val * G[i];
    printf("%.3lf",(double)ans);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP