A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2370 博物馆 概率dp 高斯消元
发表于: | 分类: Oi | 评论:0 | 阅读:42

PS:这个分类是在是太明显了,下面得 $source$ 把知识点都写出来了……

现在给出一张无向连通图,连通图上有n个点,m条边,有两个人分别站在点a和点b,现在给出他们的移动方式,对于一个在点i的人,他有Pi 的概率在这分钟内不去其他地方,有1-Pi 的概率他会在相邻的点中等可能的选择一间并沿着边走过去。问这两个人在每个点碰面的概率各为多少

用 $f(i,j)$ 表示两人分别在 $(i,j)$ 处的概率

每个状态可以拓展一发……列出了$n*n$个方程然后高斯消元,时间复杂度是$O(n^6)$

暴力的要死

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 20+2;
const int M = N * N + 4;
const double eps = 1e-13;
using namespace std;
int tot;
double p[N];
double a[M][M];
int table[N][N];
bool in[N][N];
int deg[N],n,m;

void build(int x1,int x2)
{
    a[table[x1][x2]][table[x1][x2]]--;
    for(int i=1;i<=n;++i)
        if(in[x1][i])
            for(int j=1;j<=n;++j)
                if(in[x2][j])
                    if(i!=j)
                    {
                        if(i==x1 && j==x2) a[table[x1][x2]][table[i][j]] += p[i]*p[j];
                        else if(i==x1) a[table[x1][x2]][table[i][j]] += p[i]*(1-p[j])/deg[j];
                        else if(j==x2) a[table[x1][x2]][table[i][j]] += p[j]*(1-p[i])/deg[i];
                        else a[table[x1][x2]][table[i][j]] += (1-p[i])*(1-p[j])/deg[i]/deg[j];
                    }
}

int S,T;

int main()
{
    cin >> n >> m >> S >> T;
    for(int i=1,x,y;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        deg[x]++,deg[y]++;in[x][y] = in[y][x] = 1;
    }
    int cnt = 0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            table[i][j] = ++cnt;

    a[table[S][T]][cnt+1] = -1;
    for(int i=1;i<=n;++i) in[i][i] = 1;
    for(int i=1;i<=n;++i) scanf("%lf",&p[i]);

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            build(i,j);

    for(int i=1;i<=cnt;++i)
    {
        int tt = i;
        for(int j=1;j<=cnt;++j)
            if(fabs(a[j][i]) > eps) tt = j;
        for(int j=1;j<=cnt+1;++j) swap(a[i][j],a[tt][j]);
        for(int j=1;j<=cnt;++j)
            if(j!=i && fabs(a[j][i]) > eps)
            {
                double tt = a[j][i] / a[i][i];
                for(int k=1;k<=cnt+1;++k)
                    a[j][k] -= a[i][k]*tt;
            }
    }

    for(int i=1;i<=n;++i)
    {
        int tmp = table[i][i];
        printf("%.6lf ",a[tmp][cnt+1]/a[tmp][tmp]);
    }
}

Title - Artist
0:00

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

TOP