【题解】洛谷 P4061 [Code+#1]大吉大利，晚上吃鸡！

· · 题解

前言

巨佬们的题解都好难懂（我是仔细阅读了 @Cyhlnj 题解中的每一句代码才弄懂的），于是我这个蒟蒻打算写一篇思路清晰、尽可能严谨的题解，如有错误还请指正。

顺带一提，这里有两组 Hack 数据。截止本文发布前（2021.8.25），本题题解区只有 FrenkiedeJong21 的题解能通过这两组数据（当然本题解的代码是可以过的），具体原因见这个帖子。

题意简述

给定 n 个点，m 条边的无向图，以及起点 S 和终点 T。求满足下列条件的无序点对 (A,B) 的数量。

条件：对于任意一条从 S 到 T 的最短路径，其恰好经过 A 和 B 其中之一。

数据范围：1 \le n,m \le 5 \times 10^4，边权 w 满足 1 \le w \le 10^9。

P.S. 本题数据可能出现从 S 出发无法到达 T 的情况。根据前人的经验，此时应输出 \binom{n}{2}=\dfrac{n(n-1)}{2}。

P.S. 为了方便叙述，默认下文中的“路径”“最短路径”等均指“从 S 到 T 的最短路径”。

分析

设 F(i) 表示经过 i 号点的路径数量，那么 F 可以通过正反两次 Dijkstra 求出。

容易想到一个满足题意的必要条件：F(A)+F(B)=F(T)，即经过 A,B 两个点的路径数之和等于总路径数。

进一步，答案应为：满足 F(A)+F(B)=F(T) 且不存在一条路径同时经过 A 和 B 的无序点对 (A,B) 的数量。（因为数量之和达到上限，所以只需保证每条路径只经过至多一个点，即：在 F(A) 和 F(B) 中至多一个提供贡献）

由于 F(A)+F(B)=F(T) 是一个简单的数量关系限制，容易处理。于是考虑如何求出不存在一条路径同时经过 A 和 B 的无序点对 (A,B)（当然不是一个一个列举出，而是计算出能代表其特征的数据），再计算出其中满足 F(A)+F(B)=F(T) 的数量。

题解

首先任取一条 S 到 T 的最短路径 P，那么 A 和 B 中恰好一个在 P 上。不妨设 A 在路径 P 上，则 B 不在路径 P 上。

结论一

对于固定的 B，使得 A 和 B 满足特殊性质的全体 A，在路径 P 上是连续的一段。（“x 和 y 满足特殊性质”指“不存在一条路径同时经过 x 和 y”，下同）

结论一证明

设 X,Y,Z 为路径 P 上顺次（“顺次”指按从 S 到 T 依次经过的顺序，不一定连续，下同）出现的三个点。假设 X 和 B，Z 和 B 都满足特殊性质，但 Y 和 B 不满足特殊性质。

那么有两种情况：

  1. 存在一条最短路径 P_1，先经过 Y 再经过 B。
    • 将路径 P_1 从 S 到 Y 的部分用路径 P 从 S 到 Y 的部分替换，得到路径 P_2。显然 P_2 也为最短路径，且 P_2 先经过 X 再经过 B，这与 X 和 B 满足特殊性质矛盾。
  2. 存在一条最短路径 P_3，先经过 B 再经过 Y。
    • 将路径 P_3 从 Y 到 T 的部分用路径 P 从 Y 到 T 的部分替换，得到路径 P_4。显然 P_4 也为最短路径，且 P_4 先经过 B 再经过 Z，这与 Z 和 B 满足特殊性质矛盾。

因此假设不成立，则结论一成立。

结论二

设 X,Y 为任意最短路径上顺次出现的两个点，则不存在最短路径先经过 Y 再经过 X。

结论二证明

设 S 到 X 的最短距离为 a，X 到 Y 的最短距离为 e，Y 到 T 的最短距离为 b，则 S 到 T 的最短路径距离为 a+e+b。再设 S 到 Y 的最短距离为 c，X 到 T 的最短路径为 d。

假设存在一条先经过 Y 再经过 X 的最短路径，则 c+e+d=a+e+b。进一步有 c \le a 且 d \ge b，或 c \ge a 且 d \le b。

若 c \le a，则 S 到 T 存在一条经过 Y 的路径，其长度为 c+b \le a+b < a+e+b。

若 d \le b，则 S 到 T 存在一条经过 X 的路径，其长度为 a+d \le a+b < a+e+b。

这与 S 到 T 的最短距离为 a+e+b 矛盾，因此假设不成立。

故结论二成立。

推论

由结论二可知：把所有最短路径看成有向路径，然后取它们的并集，所形成的有向图是一个 DAG（Directed Acyclic Graph，有向无环图）。

求解不存在路径同时经过 x 和 y 的无序点对 (x,y)

将路径 P 上的点顺次记为 p_1,p_2,\cdots,p_t，其中 t 为路径 P 上的点数。（Dijkstra 时记录每个点的前驱，即可求出某条最短路径 P 上的 p_1,p_2,\cdots,p_t）

由结论一，设路径 P 上和 i 号点有特殊性质的全体点为 p_{L(i)},p_{L(i)+1},\cdots,p_{R(i)}（L(i)>R(i) 表示不存在），则有如下等式：

L(i)=\max_{p_{_k} \to i}k+1 R(i)=\min_{i \to p_{_k}}k-1

其中条件 x \to y 表示存在先经过 x 再经过 y 的最短路径。

为了便于计算，我们将其改成递推形式：

j+1 \quad (i=p_j)\\ \max_{(k,i) \in E}L(k) \quad (\text{otherwise}) \end{cases} j-1 \quad (i=p_j)\\ \min_{(i,k) \in E}R(k) \quad (\text{otherwise}) \end{cases}

其中条件 (x,y) \in E 表示 x 和 y 之间存在直接相连的边，且存在一条最短路径先经过 x 再经过 y。

由推论可知，由于有向最短路径的并集形成的图是 DAG，可以使用拓扑排序对 L 和 R 进行转移。（即：只考虑最短路径可能经过的边，进行拓扑排序）

求解其中满足 F 之和等于 F(T) 的无序点对数量

由上一部分知，所有的、不存在路径同时经过 x 和 y 的无序点对 (x,y) 为全体 (i,p_j)，其中 i 不在路径 P 上且 j \in [l(i),r(i)]。

至此，只需解决最后一个问题：对于每个 i，求出满足 j \in [l(i),r(i)] 且 F(i)+F(p_j)=F(T) 的 j 的数量。

拿一个 map 当桶，在计算 p_{l(i)} 的贡献前把值 F(i) 加入，在计算 p_{r(i)} 的贡献后把值 F(i) 删除，F(i)+F(p_j)=F(T) 的 i 的数量即为计算时 map 中值 F(T)-F(p_j) 的数量。

注意：在本题的限制下，起点 S 到终点 T 的最短路径数量 F 可以达到指数级别。因此，要将最短路径的数量 F 对大质数取模，否则可以被【前言】中提到的 Hack 数据 Hack。

时间复杂度分析

堆优化 Dijkstra 是 O(m\log{m}) 的，拓扑排序是 O(m) 的，map 的加入、删除、查询次数为 O(n)，因此总时间复杂度为 O(m\log{m}+n\log{n})。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,S,T;
const int max_n=5e4+5;
const int max_m=5e4+5;
int End[max_m<<1],Last[max_n],Next[max_m<<1],Len[max_m<<1],e;
inline void add_edge(int x,int y,int z)
{
    End[++e]=y,Next[e]=Last[x],Last[x]=e,Len[e]=z;
    End[++e]=x,Next[e]=Last[y],Last[y]=e,Len[e]=z;
}
typedef pair<long long,int> P;
priority_queue<P,vector<P>,greater<P> > Q;
long long dis[2][max_n];
const int mod=1e9+7;
inline void add(int &a,int b)
{
    a=a+b-(a+b>=mod?mod:0);
}
inline int get_dif(int a,int b)
{
    return a-b+(a<b?mod:0);
}
int f[2][max_n],pre[max_n];
inline void Dijkstra(int op)
{
    for(int i=1;i<=n;++i)
        dis[op][i]=1e18;
    if(!op)
    {
        dis[op][S]=0,f[op][S]=1;
        Q.push(P(0,S));
    }
    else
    {
        dis[op][T]=0,f[op][T]=1;
        Q.push(P(0,T));
    }
    while(Q.size())
    {
        long long d=Q.top().first;
        int x=Q.top().second;
        Q.pop();
        if(dis[op][x]<d)
            continue;
        for(int i=Last[x];i;i=Next[i])
        {
            int y=End[i];
            if(d+Len[i]<dis[op][y])
            {
                dis[op][y]=d+Len[i];
                f[op][y]=f[op][x];
                if(op)
                    pre[y]=x;
                Q.push(P(dis[op][y],y));
            }
            else if(d+Len[i]==dis[op][y])
                add(f[op][y],f[op][x]);
        }
    }
}
inline bool check(int op,int x,int y,int w)
{
    return dis[op][x]+w+dis[op^1][y]==dis[0][T];
}
int p[max_n],tot,l[max_n],r[max_n],d[max_n],que[max_n],head,tail;
inline void TopSort(int op)
{
    for(int x=1;x<=n;++x)
        for(int i=Last[x];i;i=Next[i])
        {
            int y=End[i];
            if(check(op,x,y,Len[i]))
                ++d[y];
        }
    head=1,tail=0;
    for(int i=1;i<=n;++i)
    {
        if(!d[i])
            que[++tail]=i;
    }
    while(head<=tail)
    {
        int x=que[head++];
        for(int i=Last[x];i;i=Next[i])
        {
            int y=End[i];
            if(check(op,x,y,Len[i]))
            {
                op?r[y]=min(r[x],r[y]):l[y]=max(l[x],l[y]);
                if(!--d[y])
                    que[++tail]=y;
            }
        }
    }
    assert(tail==n);
}
int F[max_n];
vector<int> id_l[max_n],id_r[max_n];
map<int,int> cnt;
int main()
{
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    Dijkstra(0);
    if(dis[0][T]==1e18)
    {
        printf("%lld\n",n*(n-1ll)>>1);
        return 0;
    }
    Dijkstra(1);
    for(int i=S;i;i=pre[i])
        p[++tot]=i,l[i]=tot+1,r[i]=tot-1;
    for(int i=1;i<=n;++i)
    {
        if(dis[0][i]+dis[1][i]==dis[0][T])
            F[i]=1ll*f[0][i]*f[1][i]%mod;
        if(!l[i])
            l[i]=1,r[i]=tot;
    }
    TopSort(0),TopSort(1);
    for(int i=1;i<=n;++i)
    {
        if(l[i]<=r[i])
        {
            id_l[l[i]].push_back(i);
            id_r[r[i]].push_back(i);
        }
    }
    long long ans=0;
    for(int i=1;i<=tot;++i)
    {
        for(vector<int>::iterator it=id_l[i].begin();it!=id_l[i].end();++it)
            ++cnt[F[*it]];
        ans+=cnt[get_dif(F[T],F[p[i]])];
        for(vector<int>::iterator it=id_r[i].begin();it!=id_r[i].end();++it)
            --cnt[F[*it]];
    }
    printf("%lld\n",ans);
    return 0;
}