[CF1067E]Random Forest Rank

Link

给定一个森林,每条边有\frac 12的概率被删去,随机删掉一些边,求剩下的图的临界矩阵的秩的期望值。

Solution

满秩的矩阵的行列式不为0。结合行列式的定义|A|=\sum_{\pi_i}(-1)^{\delta(\pi_i)}\prod a_{\pi_{ij}}。对于一个行列式不为零的邻接矩阵,其必要条件是\exist \pi_i,\text{s.t.}\prod a_{\pi_{ij}}\not=0
\pi_i循环分解,循环内相邻的点都有边连接。然而,对于一个不存在环的森林,这样的循环大小只能为2——即一条边连接的两个点。因此,求出这个森林的最大匹配,设为m,那么就能选出一个大小为2m的点集,其邻接矩阵满足\exist \pi_i,\text{s.t.}\prod a_{\pi_{ij}}\not=0的条件。
另外,选出的这个点集,完美匹配是唯一的,因此,只会有一个\pi_i满足上式子。
由此,问题转化为求期望最大匹配。
然后就不会了 先坑着吧

Code

[cf1051F]The shortest statement

Link

n个点,m(m-n< 20)条边的连通图,多组询问两点的最短路。

Solution

求出图的任意一个生成树,把不在生成树上的边所连接的点都做一遍最短路。
如果两点最短路在生成树上,那么求出树上最短路就得到答案。
否则,考虑floyd算法,选取点u,用d[x][u]+d[u][y]更新答案。选取的点u只需选取那些不在生成树上的边连接的点,因为如果生成树上的某点到点x在树上的距离不是最短路,那么最短路一定经过某个不在生成树上的边连接的点,因此只用这些点松弛就行了。