正題

題目鏈接:https://www.luogu.com.cn/problem/CF446D

---

題目大意

給出$n$個(gè)點(diǎn)$m$條邊的一張無(wú)向圖，一些點(diǎn)有陷阱，走到時(shí)會(huì)損失一條生命，總共有$k$條生命，求從$1$出發(fā)隨機(jī)游走到$n$沒(méi)有死亡且到終點(diǎn)時(shí)僅剩一條命的概率。

$1\le n\le 500,1\le m\le 10^5,2\le k\le 10^9$

陷阱點(diǎn)個(gè)數(shù)不超過(guò)$100$。

---

解題思路

這個(gè)$k$很大，這個(gè)陷阱點(diǎn)個(gè)數(shù)又很少，我們可以考慮矩陣乘法，預(yù)處理$a_{i,j}$表示陷阱點(diǎn)$i$走到陷阱點(diǎn)$j$且中間沒(méi)有走陷阱點(diǎn)的概率，然后矩陣乘法轉(zhuǎn)移即可。

但是現(xiàn)在的問(wèn)題是我們?nèi)绾慰焖兕A(yù)處理出$a_{i,j}$，可以考慮枚舉終點(diǎn)$x$那么有$f_x=1$，然后其他的陷阱點(diǎn)處$f_x=0$，一般的點(diǎn)處$f_x=\frac{1}{de{g}_x}{\sum }_{x\to y}{f}_y$，這樣我們就能對(duì)于每個(gè)起點(diǎn)預(yù)處理出$g_{i,j}$表示從無(wú)陷阱的節(jié)點(diǎn)$i$走到陷阱點(diǎn)$j$且中間沒(méi)有其他陷阱點(diǎn)的概率。

之后我們枚舉起點(diǎn)陷阱點(diǎn)的出邊就可以預(yù)處理出$a$了，因?yàn)樯厦娴倪^(guò)程要用到高斯消元，所以這樣的復(fù)雜度是$O(n^4)$的，無(wú)法通過(guò)本題。

不難注意到上面的消元中，我們只有陷阱點(diǎn)處的常數(shù)（且陷阱點(diǎn)處僅有常數(shù)）發(fā)生了變化，所以我們可以直接高斯消出每個(gè)非陷阱點(diǎn)和所有陷阱點(diǎn)的關(guān)系式，然后直接帶入常數(shù)即可。

記陷阱點(diǎn)個(gè)數(shù)為$r$，時(shí)間復(fù)雜度$O((n+r{)}^3+r^3\log k)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int N=610,S=110; const double eps=1e-8; struct matrix{double a[S][S]; }ans,m,c; matrix operator*(const matrix &a,const matrix &b){memset(c.a,0,sizeof(c.a));for(int i=0;i<S;i++)for(int j=0;j<S;j++)for(int k=0;k<S;k++)c.a[i][j]+=a.a[i][k]*b.a[k][j];return c; } int n,h,k,deg[N],a[N][N]; double f[N][N];bool v[N]; vector<int> q; int main() {scanf("%d%d%d",&n,&h,&k);for(int i=1;i<=n;i++){scanf("%d",&v[i]);if(v[i]){q.push_back(i);f[i][n+q.size()]=f[i][i]=1;}}int r=n+q.size();for(int i=1,x,y;i<=h;i++){scanf("%d%d",&x,&y);a[x][y]++;a[y][x]++;deg[x]++;deg[y]++;}for(int i=1;i<=n;i++){if(v[i])continue;for(int j=1;j<=n;j++)f[i][j]=-1.0*a[i][j]/(double)deg[i];f[i][i]=1;}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++)if(fabs(f[i][j])>eps){swap(f[i],f[j]);break;}double d=f[i][i];for(int j=i;j<=r;j++)f[i][j]=f[i][j]/d;for(int j=1;j<=n;j++){if(i==j)continue;double rate=-f[j][i]/f[i][i];for(int k=i;k<=r;k++)f[j][k]+=rate*f[i][k];}}for(int i=0;i<q.size();i++)ans.a[0][i]=f[1][n+i+1];for(int i=0;i<q.size();i++){for(int j=0;j<q.size();j++){for(int k=1;k<=n;k++)m.a[i][j]+=a[q[i]][k]*f[k][n+j+1];m.a[i][j]/=(double)deg[q[i]];}}k-=2;while(k){if(k&1)ans=ans*m;m=m*m;k>>=1;}printf("%.10lf\n",ans.a[0][q.size()-1]);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的CF446D-DZY Loves Games【高斯消元,矩阵乘法】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。