BZOJ 1778: [Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元+期望dp)

传送门

解题思路

　　设\(f(x)\)表示到\(x\)这个点的期望次数，那么转移方程为\(f(x)=\sum\frac{f(u)*(1 - \frac{p}{q})}{deg(u)}\)，其中\(u\)为与\(x\)相连的点，\(deg(u)\)为\(u\)的度数。转移方程很好理解的，而每个点的爆炸概论就等于\(f(x)*\frac{p}{q}\)。之后做一遍高斯消元就行了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;
const int N=305;
const double eps=1e-13;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=ch==‘-‘?0:1,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar();
    return f?x:-x;
}

int n,m,P,Q,deg[N];
double X[N][N],boom;
vector<int> v[N];

inline void gauss(){
    for(int i=1;i<=n;i++){
        int p=-1; double Mx=0;
        for(int j=i;j<=n;j++)
            if(fabs(X[j][i])-eps>Mx) Mx=fabs(X[j][i]),p=j;
        if(p==-1) continue;
        if(p!=i) for(int j=i;j<=n+1;j++) swap(X[i][j],X[p][j]);
        for(int j=1;j<=n;j++){
            if(j==i) continue;
            double tmp=X[j][i]/X[i][i];
            for(int k=i;k<=n+1;k++) X[j][k]-=X[i][k]*tmp; 
        }
    }
}

inline void print(){
    for(int i=1;i<=n;i++)
        printf("%.9lf\n",X[i][n+1]/X[i][i]*boom);
}

int main(){
    n=rd(),m=rd(),P=rd(),Q=rd(); int x,y;
    boom=(double)P/Q;
    for(int i=1;i<=m;i++) {
        x=rd(),y=rd(); deg[x]++,deg[y]++;
        v[x].push_back(y); v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        X[i][i]=1;
        for(int j=0;j<v[i].size();j++)
            X[i][v[i][j]]=-(1-boom)/deg[v[i][j]];
    }   
    X[1][n+1]=1; gauss(); print();
    return 0;
}

BZOJ 1778: [Usaco2010 Hol]Dotp 驱逐猪猡(高斯消元+期望dp)

原文：https://www.cnblogs.com/sdfzsyq/p/10280872.html