[bzoj5109]-[CodePlus 2017]大吉大利,晚上吃鸡!

吃鸡专用(雾)

题目(BZOJ)

题目(LibreOJ)

来说说这题吧

首先肯定要求 $s$ 到 $t$ 的最短路径条数,我们就根据这个来做。

一对 $(A,B)$ 满足条件,则 $s$ 到 $A$ 到 $t$ 的路径条数$+s$ 到 $B$ 到 $t$ 的路径条数$==s$到 $t$ 的路径条数,这个很显然,

于是我们设 $sum[0][i]$ 表示从 $s$ 出发到i的最短路径条数,$sum[1][i]$ 表示从 $t$ 出发到 $i$ 的最短路径条数,

则条件一转化为: $sum[0][A]\times sum[1][A]+sum[0][B]\times sum[1][B]=sum[0][t]$ ,

移一下项:$sum[0][A]\times sum[1][A]=sum[0][t]-sum[0][B]\times sum[1][B]$,

所以我们将 $sum[0][A]\times sum[1][A]$ 作为状态存入一个 map 中,也就相当于把    $sum[0][t]-sm[0][B]*sum[1][B]$ 存入 map 中。

同时,我们再开一个 $g$ 数组,表示 $A$ 与 $B$ 相互可达性。

然后就做完了。

总而言之,算法流程如下:

  1. 正反各一次求一遍最短路,更新 $sum$ 数组;
  2. 预处理满足 $sum[0][i]+sum[1][i]==sum[0][t]$ 的点,放到 $p$ 数组中,并且预处理这个 map;
  3. 对 $p$ 数组中的点正反各一次拓扑排序,更新 $g$ 数组;
  4. 最后做个统计,完毕。

不过这题有 $s$ 和 $t$ 不联通的情况……直接输出 $\frac{n(n-1)}{2}$ 即可。

发表评论