题目
题目链接：https://www.luogu.com.cn/problem/P7293
Bessie 有一些无向连通图 \(G_1,G_2,…,G_K\)。对于每一个 \(1≤i≤K\)，\(G_i\) 有 \(N_i\) 个编号为 \(1…N_i\) 的结点与 \(M_i\) 条边。\(G_i\) 可能含有自环，但同一对结点之间不会存在多条边。
现在 Elsie 用 \(N_1⋅N_2⋯N_K\) 个结点建立了一个新的无向图 \(G\)，每个结点用一个 \(K\) 元组 \((j_1,j_2,…,j_K)\) 标号，其中 \(1≤j_i≤N_i\)。若对于所有的 \(1≤i≤K\)，\(j_i\) 与 \(k_i\) 在 \(G_i\) 中连有一条边，则在 \(G\) 中结点 \((j_1,j_2,…,j_K)\) 和 \((k_1,k_2,…,k_K)\) 之间连有一条边。
定义 \(G\) 中位于同一连通分量的两个结点的 距离 为从一个结点到另一个结点的路径上的最小边数。计算 \(G\) 中结点 \((1,1,…,1)\) 与所有与其在同一连通分量的结点的距离之和，对 \(10^9+7\) 取模。
\(\sum N_i\leq 10^5\)，\(\sum M_i\leq 2\times 10^5\)。
思路
首先把题目多读几遍。
如果点 \((1,1,\cdots ,1)\) 可以通过 \(d\) 步到达 \((j_1,j_2,\cdots j_k)\)，当且仅当在第 \(i(i\in[1,k])\) 张图上，存在一条长度为 \(d\) 的起点为 \(1\)，终点为 \(j_i\) 的路径。
由于可以在一条边上反复横跳，所以我们只需要求出每一张图上的每一个点，到点 \(1\) 长度为奇数/偶数的最短路 \(dis[x][0/1]\)。
然后不难发现，点 \((1,1,\cdots ,1)\) 到点 \((j_1,j_2,\cdots j_k)\) 的最短路就是
这个东西看着就很烦，但是他等价于
那么我们分别令点 \(i\) 的权值 \(a_i\) 为这三个东西，然后跑三次求出来就好了。
将二元组 \((a_i,i)\) 按照 \(a_i\) 从小到大排序，依次枚举每一个二元组。其中一个二元组 \((a_i,i)\) 作为最大值的方案数，就是前面二元组，除 \(i\) 所在的图以外，其他图的点数的乘积。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=100010,M=400010,MOD=1e9+7,Inf=1e9;
int n,m,t,tot,cnt,c[N],head[N],bel[N],dis[N][2];
ll ans,res;
pair<int,int> a[N];
struct edge
{
int next,to;
}e[M];
void add(int from,int to)
{
e[++tot]=(edge){head[from],to};
head[from]=tot;
}
void bfs(int s)
{
queue<pair<int,int> > q;
q.push(mp(s,0)); dis[s][0]=0;
while (q.size())
{
int u=q.front().fi,id=q.front().se;
q.pop();
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[v][id^1]>dis[u][id]+1)
{
dis[v][id^1]=dis[u][id]+1;
q.push(mp(v,id^1));
}
}
}
}
ll fpow(ll x,ll k)
{
ll ans=1;
for (;k;k>>=1,x=x*x%MOD)
if (k&1) ans=ans*x%MOD;
return ans;
}
void solve(int tag)
{
sort(a+1,a+1+n);
res=0; cnt=0;
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
{
if (a[i].fi>Inf) return;
int bl=bel[a[i].se];
cnt+=(!c[bl]); c[bl]++;
if (cnt==t)
{
res=1; cnt++;
for (int j=1;j<=t;j++)
if (j!=bl) res=res*c[j]%MOD;
}
else res=res*fpow(c[bl]-1,MOD-2)%MOD;
ans=(ans+1LL*tag*a[i].fi*res)%MOD;
res=res*c[bl]%MOD;
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(dis,0x3f,sizeof(dis));
scanf("%d",&t);
for (int k=1;k<=t;k++)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) bel[cnt+i]=k;
for (int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
x+=cnt; y+=cnt;
add(x,y); add(y,x);
}
bfs(cnt+1);
cnt+=n;
}
n=cnt;
for (int i=1;i<=n;i++)
a[i]=mp(dis[i][0],i);
solve(1);
for (int i=1;i<=n;i++)
a[i]=mp(dis[i][1],i);
solve(1);
for (int i=1;i<=n;i++)
a[i]=mp(max(dis[i][0],dis[i][1]),i);
solve(-1);
printf("%lld",(ans%MOD+MOD)%MOD);
return 0;
}