青海省教育厅门户网站登录,简约式网站模板,wordpress能开发商城网站吗,信息门户网站怎么做正题
题目链接:https://www.luogu.com.cn/problem/CF446D 题目大意
给出nnn个点mmm条边的一张无向图#xff0c;一些点有陷阱#xff0c;走到时会损失一条生命#xff0c;总共有kkk条生命#xff0c;求从111出发随机游走到nnn没有死亡且到终点时仅剩一条命的概率。 1≤n≤…正题
题目链接:https://www.luogu.com.cn/problem/CF446D 题目大意
给出nnn个点mmm条边的一张无向图一些点有陷阱走到时会损失一条生命总共有kkk条生命求从111出发随机游走到nnn没有死亡且到终点时仅剩一条命的概率。
1≤n≤500,1≤m≤105,2≤k≤1091\leq n\leq 500,1\leq m\leq 10^5,2\leq k\leq 10^91≤n≤500,1≤m≤105,2≤k≤109
陷阱点个数不超过100100100。 解题思路
这个kkk很大这个陷阱点个数又很少我们可以考虑矩阵乘法预处理ai,ja_{i,j}ai,j表示陷阱点iii走到陷阱点jjj且中间没有走陷阱点的概率然后矩阵乘法转移即可。
但是现在的问题是我们如何快速预处理出ai,ja_{i,j}ai,j可以考虑枚举终点xxx那么有fx1f_x1fx1然后其他的陷阱点处fx0f_x0fx0一般的点处fx1degx∑x→yfyf_x\frac{1}{deg_x}\sum_{x\rightarrow y}f_{y}fxdegx1∑x→yfy这样我们就能对于每个起点预处理出gi,jg_{i,j}gi,j表示从无陷阱的节点iii走到陷阱点jjj且中间没有其他陷阱点的概率。
之后我们枚举起点陷阱点的出边就可以预处理出aaa了因为上面的过程要用到高斯消元所以这样的复杂度是O(n4)O(n^4)O(n4)的无法通过本题。
不难注意到上面的消元中我们只有陷阱点处的常数且陷阱点处仅有常数发生了变化所以我们可以直接高斯消出每个非陷阱点和所有陷阱点的关系式然后直接带入常数即可。
记陷阱点个数为rrr时间复杂度O((nr)3r3logk)O((nr)^3r^3\log k)O((nr)3r3logk) code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includevector
using namespace std;
const int N610,S110;
const double eps1e-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 i0;iS;i)for(int j0;jS;j)for(int k0;kS;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];
vectorint q;
int main()
{scanf(%d%d%d,n,h,k);for(int i1;in;i){scanf(%d,v[i]);if(v[i]){q.push_back(i);f[i][nq.size()]f[i][i]1;}}int rnq.size();for(int i1,x,y;ih;i){scanf(%d%d,x,y);a[x][y];a[y][x];deg[x];deg[y];}for(int i1;in;i){if(v[i])continue;for(int j1;jn;j)f[i][j]-1.0*a[i][j]/(double)deg[i];f[i][i]1;}for(int i1;in;i){for(int ji;jn;j)if(fabs(f[i][j])eps){swap(f[i],f[j]);break;}double df[i][i];for(int ji;jr;j)f[i][j]f[i][j]/d;for(int j1;jn;j){if(ij)continue;double rate-f[j][i]/f[i][i];for(int ki;kr;k)f[j][k]rate*f[i][k];}}for(int i0;iq.size();i)ans.a[0][i]f[1][ni1];for(int i0;iq.size();i){for(int j0;jq.size();j){for(int k1;kn;k)m.a[i][j]a[q[i]][k]*f[k][nj1];m.a[i][j]/(double)deg[q[i]];}}k-2;while(k){if(k1)ansans*m;mm*m;k1;}printf(%.10lf\n,ans.a[0][q.size()-1]);return 0;
}
