《大吉大利，晚上吃鸡！》题解

出题人：陈宇

验题人：刑健开(jkxing)

题目简述

给定一张有边权（边权全为正）的无向图， n 个点m条边，给定起点 S 和终点T，问有多少对 A 和B满足从 S 到T的任意最短路一定经过 A 或者B，但是不存在某条最短路同时经过 A 和B。

解法一

首先是最暴力的解法，枚举任意点对 A 和B，然后删掉 A 和B，看看最短距离是否会变长，然后查看 dis(S,A)+dis(A,B)+dis(B,T) 是否和 dis(S,T) 相等，其中 dis(X,Y) 表示原图中点 X 到Y的最短距离，由此可以判断枚举的 A 和B是否是合法的点对。

其中， dis(X,Y) 可以用floyd求解

时间复杂度： O(n3)

期望得分： 30

解法二

首先，虽然题目中给定的是无向图，但是实际上我们可以先从 S 出发求一遍最短路，然后问题变成了：“在有向无环图上，求有多少个满足条件的点对A,B,满足从 S 到T的所有路径一定经过 A,B 其中一点，并且不存在路径同时经过 A,B ”。

求解这到题目的一个关键点在于：满足条件的点对 A,B 具有特点：从 S 到A的方案数 × 从 A 到T的方案数 + 从 S 到B的方案数 × 从 B 到T的方案数 = 从S到 T 的方案数。

所以在有向无环图上用动态规划求解路径条数，再去掉A可以到达 B 或B可以到达 A 的情况即可求解这到题目。

PS：方案数可能会爆掉怎么办？可以对方案数求余一个大整数，如果觉得不够的话可以求余两个大整数。

时间复杂度：O(n2+n∗m)

期望得分： 60

解法三

在解法二中，定义 F(X)= 从 S 到X的方案数 × 从 X 到T的方案数 = 从 S 经过X到达 T 的方案数，所以满足条件的点对A,B为:

F(A)+F(B)=F(T)A 和B不能相互到达

对于条件 1 ，我们可以使用数据结构进行优化（使用std::map即可），而对于条件2，我们可以使用 bitset 位压 32 或者 64 位进行加速，使得最终时间和空间都能够承受。

时间复杂度： O(n∗log(n)+n∗m/32)

期望得分： 100

如果觉得《清华月赛 大吉大利晚上吃鸡题解》对你有帮助，请点赞、收藏，并留下你的观点哦！