P7293 [USACO21JAN] Sum of Distances P（图论，bfs）

· · 题解

简单的线性做法。

从新图的起点走到 (a_1,a_2...a_k)，相当于在 k 张图上同时从 1 走到 a_i。

如果某张图比其他图先走到，那么这个点可以任选一条经过它的边反复横跳。

所以只需要保证每张图上从 1 走到 a_i 距离的奇偶性相同。

首先通过 bfs，预处理每张图上 1 到所有点的长度为奇数和偶数的最短路。

记 ji_i 为奇数最短路，ou_i 为偶数最短路，若不存在则为 \inf。

则新图的起点到 (a_1,a_2...a_k) 的距离，等于 \min(\max(ji_{a_i}),\max(ou_{a_i}))。

这个式子不好处理，通过 a+b=\min(a,b)+\max(a,b)，转化为 \max(ji_{a_i})+\max(ou_{a_i})-\max(\max(ji_{a_i},ou_{a_i}))。

将三部分分别计算，每次分别记 w_i=ji_i,ou_i,\max(ji_i,ou_i)。

考虑对于每个点 j，求出 j\in a_i，且 w_j=\max(w_{a_i}) 的方案数。

发现这样会算重，考虑对于相同的 w_j，按所属图的编号为第二关键字比较。

于是只需要将所有点按 w_j 为第一关键字，图的编号为第二关键字排序，因为值域是点数级别，所以这部分复杂度是线性。

然后按顺序依次加入每个点，加入属于图 k 的点 j 时的方案数，就是除 k 以外所有图已经被加入的点的个数的乘积。

预处理乘法逆元可以 O(1) 加点。

总复杂度线性。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3,P=1e9+7;
basic_string<int>v[3][N+1];
int iv[N],a[N],o,u;
void in(){
    int n,m,i,j;
    basic_string<int>ji,ou;
    vector<basic_string<int>>g;
    queue<int>q;
    scanf("%d%d",&n,&m),ji.assign(n+1,N),ou.assign(n+1,N),g.resize(n+1);
    while(m--)scanf("%d%d",&i,&j),g[i]+=j,g[j]+=i;
    q.push(1),ou[1]=0;
    while(q.size()){//bfs
        i=q.front(),q.pop();
        if(i>n){
            i-=n;
            for(int j:g[i])if(ou[j]==N)ou[j]=ji[i]+1,q.push(j);
        }else for(int j:g[i])if(ji[j]==N)ji[j]=ou[i]+1,q.push(j+n);
    }
    for(i=1;i<=n;++i)v[0][ji[i]]+=u,v[1][ou[i]]+=u,v[2][max(ji[i],ou[i])]+=u;
}
int get(basic_string<int>*v){
    int i,s=0,t=1,c=0;
    for(i=0,memset(a,0,N*4);i<N;++i)for(int j:v[i]){//加点
        if(a[j])t=t*1ll*iv[a[j]]%P;else ++c;
        if(c==o)s=(s+t*1ll*i)%P;
        t=t*1ll*(++a[j])%P;
    }
    return s;
}
int main(){
    for(iv[1]=1,u=2;u<N;++u)iv[u]=(P-P/u)*1ll*iv[P%u]%P;//预处理逆元
    for(scanf("%d",&o),u=1;u<=o;++u)in();
    printf("%d",((get(v[0])+get(v[1])-get(v[2]))%P+P)%P);
    return 0;
}