主题

主题

 
   

1778: [Usaco2010 Hol]Dotp 驱逐猪猡

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=1778/https://www.luogu.org/problem/show?pid=2973

Description

奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。

猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城。这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<= N; 1 <= B_j <= N)表示的双向道路连接。保证城市1至少连接一个其它的城市。

一开始臭气弹会被放在城市1。每个小时(包括第一个小时),它有P/Q (1 <= P <=1,000,000; 1 <= Q <= 1,000,000)的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市,那麽它随机地选择一条道路,在这个小时内沿着这条道路走到一个新的城市。可以离开这个城市的所有道路被选择的概率均等。

因为这个臭气弹的随机的性质,奶牛们很困惑哪个城市最有可能被污染。

给定一个猪猡文明的地图和臭气弹在每个小时内爆炸的概率。计算每个城市最终被污染的概率。

如下例:

假设这个猪猡文明有两个连接在一起的城市。

臭气炸弹从城市1出发,每到一个城市,它都有1/2的概率爆炸。 

1--2 可知下面这些路径是炸弹可能经过的路径(最后一个城市是臭气弹爆炸的城市): 1: 1 2: 1-2 3: 1-2-1 4: 1-2-1-2 5: 1-2-1-2-1 ... 要得到炸弹在城市1终止的概率,我们可以把上面的第1,第3,第5……条路径的概率加起来,(也就是上表奇数编号的路径)。

上表中第k条路径的概率正好是(1/2)^k,也就是必须在前k-1个回合离开所在城市(每次的概率为1 - 1/2 = 1/2)并且留在最后一个城市(概率为1/2)。

所以在城市1结束的概率可以表示为1/2 + (1/2)^3 + (1/2)^5 + ...。

当我们无限地计算把这些项一个个加起来,我们最后会恰好得到2/3,也就是我们要求的概率,大约是0.666666667。

这意味着最终停留在城市2的概率为1/3,大约为0.333333333。

Input

* 第1行: 四个由空格隔开的整数: N, M, P, 和 Q * 第2到第M+1行: 第i+1行用两个由空格隔开的整数A_j和B_j表示一条道路。

Output

* 第1到第N行: 在第i行,用一个浮点数输出城市i被摧毁的概率。误差不超过10^-6的答桉会 被接受(注意这就是说你需要至少输出6位有效数字使得答桉有效)。

Sample Input

2 1 1 2

1 2

Sample Output

0.666666667

0.333333333


个人解法:

学到了一些新姿势。

不难设计出状态F[x][t]表示在t时间走到了x的概率,初始状态F[1][1]=0(我们假设时间从1开始)。

接下来我们也不难写出方程:F[x][t]=sigma(F[y][t-1]*(1-P/Q)/Ord[y]),其中(x,y)∈E,Ord是点的度数。

同样也不难得到在x爆炸的概率就是所有时间t的F[x]之和*P/Q。

但是唯一困难的是该做到什么时候停止。因为t的范围是正无穷。

这里我们需要用到矩阵。(因为变换可以表示为矩阵,而矩阵可以收敛)

首先用矩阵表示状态的转移:


因此,我们令s是一个行向量,记录答案,E是变换方阵,这个方阵是根据图很好构造的。T是一个行向量,表示初始的矩阵,不难看出,T是第一项为1,之后项为0的向量。

关于E的构造:

我们把一条双向边拆分为两条单向边,对于一条单向边<u,v>,F[u]会对F[v]造成贡献。也就是说,如果存在<u,v>一条单向边,那么就令E[u][v]=(1-P/Q)/Ord[u]。

拿到这几个向量,我们也可以得到这样一个式子:


接下来我们对右边无穷大的式子收敛一次,课得到事实上sigma(E^i)=1/(1-E)。

之后我们移项,即可得:

s*(1-E)=P/Q*T

注意,在上述的所有推导中,均忽略了矩阵不能乘法交换律。上述所有式子中,乘法是无序的。

我们发现,式子右边是一个行向量,左边是一个方阵与一个行向量。

想到高斯消元中的矩阵表达式中,左边是一个方阵与一个列向量,右边是一个列向量。

于是我们对这个式子做一个置换。(这个说法似乎不是很标准),我们需要“一个行向量*一个方阵=一个列向量”的形式,转换为“一个方阵*一个列向量=一个列向量”的形式

把方阵沿主对角线对折,所有行向量顺时针旋转π/2。这两个式子等价。

比方说:


然后就可以做高斯消元了。


代码如下:

https://code.csdn.net/snippets/2259526

 
 
评论