Luogu2973 Driving Out the Piggies G(高斯消元)题解

发布于 2021-03-19  350 次阅读


本文同步发表在我的洛谷博客,Latex炸了可以去那里看。

题目大意:

一个 $n$ 个点 $m$ 条边的无向图,节点 $1$ 有一个炸弹,在每个单位时间内,有 $p/q$ 的概率在这个节点炸掉,有 $1-\frac p q$ 的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。
$ 1 \le n \le 300$ ,$1\le m \le 50000$ 。

样例分析:

对于样例:

2 1 1 2
1 2

在 $1$ 的概率: $(1/2)^1+(1/2)^3+(1/2)^5......(1/2)^{2n+1}=2/3$
(即:一开始就爆炸或者 "1->2->1" 然后爆炸......以此类推,下面同理)
结束在 $2$ 的概率同理,为 $(1/2)^2+(1/2)^4+......+(1/2)^{2n}=1/3$

思路:

群众:分析一堆看起来很有道理,但是没有用啊?!

咳咳,至少我们可以发现路径的可能条数是无穷的(只要炸弹一直不爆炸,人就可以在两座城市之间反复横跳)。

那么对于这种奇怪的题目,我们一般考虑 使用方程来推出相邻两个状态之间的关系,从而解决无穷无尽的路径

我们设 $f_i$ 为炸弹在第 $i$ 座城市爆炸的概率。

那么对于一座城市 $x$ ,我们考虑怎么列出式子:
考虑当前城市的炸弹是从其他城市传过来并且在当前城市爆炸:
$ fx=\sum{ 所有满足 x,v有边相连的 v } \frac {(1-\frac p q)} {deg[v]}*f_v $

移项后变为:

$ -fx+\sum{ 所有满足 x,v有边相连的 v } \frac {(1-\frac p q)} {deg[v]}*f_v=0 $

也就可以对应进代码里的系数了。

对了,最后还要算上炸弹在第一座城市爆炸的概率嗷,不明白可以看代码。

诶,那我们每个城市一个方程,总共就是 $n$ 元 $n$ 个方程,用高斯消元解就好了(别跟我说你不会高斯消元)。

代码:

#include
using namespace std;
const int N=305,M=50005;

struct Edge{
    int vet,nxt;
}e[M<<1];

int n,m,edge=0,head[N],deg[N];
double p,q,a[N][N];
bool Free[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

namespace Gauss{

    bool Inf_solution=false,No_Solution=false;

    inline void SwapLine(int x,int y){      //交换第 x 行和第 y 行
        for (int i=1;i<=n+1;++i)
            swap(a[x][i],a[y][i]);
    }

    inline void Mul(int x,double k){        //把第 x 行的值乘上 k
        for (int i=1;i<=n+1;++i)
            a[x][i]*=k;
    }

    inline void Add(int x,double k,int y){      //把第 x 行乘上 k 加到第 y 行上
        for (int i=1;i<=n+1;++i)
            a[y][i]+=(a[x][i]*k);
    }

    inline void Main(){
        for (int i=1;i<=n;++i){
            if (a[i][i]==0){        //如果第 i 行第 i 项系数为 0 则与之后与不为 0 的行交换
                bool flag_free=true;
                for (int j=i+1;j<=n;++j)
                    if (a[j][i]){
                        SwapLine(i,j);
                        flag_free=false;
                        break;
                    }
                if (flag_free) Free[i]=true;
            }
            if (Free[i]) { Inf_solution=true; continue; }
            Mul(i,1.0/a[i][i]);     //把第 i 行第 i 项系数变成 1 
            for (int j=1;j<=n;++j)       //消去其他行第 i 项的系数
                if (i^j) Add(i,-a[j][i],j);
        }
        for (int i=1;i<=n;++i){
            bool flag_zero=true;
            for (int j=1;j<=n;++j)
                if (a[i][j]){
                    flag_zero=false;
                    break;
                }
            if ((flag_zero) && (a[i][n+1])){
                No_Solution=true;
                break;
            }
        }
    }

}

int main(){
    //freopen("Luogu2973.in","r",stdin);
    //freopen("Luogu2973.out","w",stdout);
    scanf("%d%d%lf%lf",&n,&m,&p,&q);
    for (int i=1;i<=m;++i){
        int x=read(),y=read();
        addedge(x,y);
        addedge(y,x);
        ++deg[x],++deg[y];
    }
    for (register int x=1;x<=n;++x){
        a[x][x]=-1;     //把方程移项,让右边为 0 后第 x 个元的系数为 -1 
        for (int i=head[x];i;i=e[i].nxt){
            int v=e[i].vet;
            a[x][v]=1.0*(q-p)/q/deg[v];     //把方程代进去就可以了
        }
    }
    a[1][n+1]=-p/q;     //算上一开始就爆炸的情况
    Gauss::Main();
    for (int i=1;i<=n;++i)
        printf("%.9lf\n",a[i][n+1]);
    return 0;
}

都看到这里了,各位看官是不是可以三连点个赞呢?


我们无法选择过去,但我们可以改变未来。