BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元 图论 期望概率

BZOJ2707 [SDOI2012]走迷宫 Tarjan+高斯消元

  题目链接 和BZOJ3270比较相似,都是在图上高斯消元来转移状态。 观察数据范围,可以很明显地看出来必须先Tarjan缩点,之后在强连通分量里面进行高斯消元。 一开始仿照3270写了个正着推出的式子,发现不太好搞,于是重新倒着想了一遍。 设f[i]:从i点出发走到终点的期望步数,则f···
BZOJ1093 最大半连通子图 tarjan+最长链 图论

BZOJ1093 最大半连通子图 tarjan+最长链

画画图,可以看出来强连通分量里面的肯定都是,所以缩点去环,建新图。观察一下,可以发现一个半联通子图没法跨越两条链,就是说最大的联通子图在新图上一定是一条最长链,DFS一下就可以求出来。就是统计最长链数的时候一开始只想出了再DFS一次的做法,但因为无形中又加了一维所以光荣TLE。后来才发现,最长链数只···
BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan 图论 期望概率

BZOJ2438 [中山市选2011]杀人游戏 期望概率+tarjan

考试的时候想的是警察一步一步确认凶手,还要缩减比例,所以完全想错了。警察是在同时完成所有调查工作,而且在同一个强连通分量中,警察只要调查一个人,剩下的人就都会被确认,即关系具有传递性。调查每个人,警察都有死亡的概率,所以最终存活的概率即为1-调查的人数/总人数。tarjan缩点建图,入度为0的点数即···