CF446D DZY Loves Games 题解

Luogu
Codeforces

Description.

有一张地图,\(n\) 个点 \(m\) 条边。
有一些点有障碍,进入后扣血,保证第一个房间没有,第 \(n\) 个房间有。
有一个人,初始在 \(1\),每次会等概率随机选择一条出边走过去。
初始血量为 \(K\),问从 \(1\) 走到 \(n\) 血不被扣光的概率。

保证有陷阱的房子数量不超过 \(100\),\(n\le 500\),\(K\le 10^9\)。

Solution.

首先考虑全都是陷阱怎么做,相当于有多少条路走到 \(n\) 不超过 \(K\) 步。
这个可以让汇点连自环,然后直接矩阵快速幂就行了。
我们可以考虑建一张新图,上面只有那些有陷阱的点,两点之间距离表示走过去不经过其他有陷阱点的概率。

我们需要考虑这个概率怎么算,很显然需要高消,但是怎么消。
定义 \(f_{i,j}\) 表示从 \(i\) 出发走到 \(j\) 不经过有陷阱点的概率。

\[\therefore f_{i,k}=\frac{1}{\deg(i)}\times \sum_{(i,v)\in E}f_{v,k} \]

注意到其实出发点和第二次经过这个点时这两个点不等价,第二次经过这个点时这个点等价于其他那些陷阱点。
所以我们需要复制每个陷阱点,建一个虚点,好在陷阱点数量不超过 \(100\)
把每个陷阱点周围的点贺一遍到虚点上,强制钦定周围点向它连单向边,表示结束位置。
但是我们需要对每个陷阱点跑一遍高消,总复杂度 \(O(n^4)\),肯定炸。

发现两个状态唯一的区别就是哪个陷阱是 \(1\),前面的系数全都相同。
所以可以直接对整个矩阵跑高消的同时把后面消掉。

然后就做完了。

Coding.

点击查看代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=605;typedef long double ld;
int n,m,K,dg[N],a[N][N],cg[N],rbt,rb[N];ld gs[N][N+105];
struct mat
{
	ld a[105][105];inline ld* operator[](int x) {return a[x];}
	inline void operator!() {for(int i=0;i<=rbt;i++) for(int j=0;j<=rbt;j++) a[i][j]=0;}
	inline void operator~() {!*this;for(int i=0;i<=rbt;i++) a[i][i]=1;}
	inline mat operator*(mat b)
	{
		mat r;!r;for(int k=0;k<=rbt;k++)
			for(int i=0;i<=rbt;i++) for(int j=0;j<=rbt;j++) r[i][j]+=a[i][k]*b[k][j];
		return r;
	}
	inline mat operator^(int q) {mat r,x=*this;~r;for(;q;q>>=1,x=x*x) if(q&1) r=r*x;return r;}
}mt;
int main()
{
	read(n,m,K);for(int i=1;i<=n;i++) read(cg[i]);
	for(int i=1,x,y;i<=m;i++) read(x,y),a[x][y]++,a[y][x]++,dg[x]++,dg[y]++;
	for(int i=1;i<=n;i++) if(cg[i]) rb[i]=++rbt;
	for(int i=1;i<=n;i++)
	{
		gs[i][i]=-1;for(int j=1;j<=n;j++)
			(cg[j]?gs[i][n+rb[j]]:gs[i][j])+=a[i][j]*1.0/dg[i];
	}
	for(int i=1;i<=rbt;i++) gs[i+n][i+n+rbt]=1,gs[i+n][i+n]=1;
	for(int i=1;i<=n+rbt;i++)
	{
		int ps=i;for(int j=i+1;j<=n+rbt;j++) if(abs(gs[j][i])>abs(gs[ps][i])) ps=j;
		if(abs(gs[ps][i])<1e-9) continue;
		for(int j=1;j<=n+rbt+rbt;j++) swap(gs[i][j],gs[ps][j]);
		ld qw=gs[i][i];for(int j=i;j<=n+rbt+rbt;j++) gs[i][j]/=qw;
		for(int j=i+1;j<=n+rbt;j++) {ld qw=gs[j][i];for(int k=1;k<=n+rbt+rbt;k++) gs[j][k]-=gs[i][k]*qw;}
	}
	for(int i=n+rbt;i>=1;i--) for(int j=1;j<i;j++)
		{ld qw=gs[j][i];for(int k=1;k<=n+rbt+rbt;k++) gs[j][k]-=gs[i][k]*qw;}
	//for(int i=1;i<=n+rbt;i++) for(int j=1;j<=n+rbt+rbt;j++) printf("%.5Lf%c",gs[i][j],j==n+rbt+rbt?'\n':' ');
	for(int i=1;i<=rbt;i++) mt[0][i]=gs[1][n+rbt+i];
	for(int i=1;i<=n;i++) if(cg[i]) for(int j=1;j<=rbt;j++) mt[rb[i]][j]=gs[i][n+rbt+j];
	//for(int i=0;i<=rbt;i++) for(int j=0;j<=rbt;j++) printf("%.5Lf%c",mt[i][j],j==rbt?'\n':' ');
	return mt=mt^(K-1),printf("%.10Lf\n",mt[0][rb[n]]),0;
}
上一篇:c语言中“ld返回值1退回状态”


下一篇:为Linux Mint Cinnamon的日历小程序增加中国农历显示以及其它部分参数优化