题解：P16918 [JLCPC 2026] 图

· · 题解

题意简述

给定一张简单无向连通图。选择两条不同的边删除，并要求剩余图仍然连通。

对于每条被删边，计算它的两个端点在剩余图中的最短路。求两段最短路长度之和的最小值，以及达到最小值的无序删边方案数。

解题思路

对边 e=(x,y)，记 c_e 为包含 e 的最短简单环长度。若 e 是桥，则令 c_e=\infty。

只删除 e 时，任意一条从 x 到 y 的路径与 e 都会构成一个包含 e 的环。反过来，包含 e 的环删去 e 后，也会留下从 x 到 y 的路径。因此，两端点的最短路长度恰好为 c_e-1。

若同时删除不同的边 e,f，继续删边不可能缩短距离。对应的距离之和至少为：

c_e+c_f-2

要取到这个下界，e 必须存在一条不经过 f 的最短绕路。同时，f 也必须存在一条不经过 e 的最短绕路。这两个条件也足以取到下界。

先确定答案的最小值。设全图最短环长度为 g，长度最小的另一个不同环为 h。若最短环不唯一，则 h=g。

任取一组合法删边方案。两条被删边在剩余图中的最短路，分别与原边构成两个环。第一个环包含 e 而不包含 f，第二个环则相反，所以它们一定不同。两个不同环的长度之和至少为 g+h，故答案至少为 g+h-2。

再取长度分别为 g,h 的两个不同环 C_1,C_2。两个简单环不同，因此 C_1\setminus C_2 与 C_2\setminus C_1 都非空。分别选择：

\begin{aligned} e & \in C_1\setminus C_2 \\ f & \in C_2\setminus C_1 \end{aligned}

删除 e,f 后，C_1-e 仍是 e 的两端点之间长度为 g-1 的路径，C_2-f 同理提供长度为 h-1 的路径。因此下界可以取到，最小值就是 g+h-2。

还需从所有 c_e 中求出 g,h。由 c_e 的定义可知，c_e=g 当且仅当 e 属于某个最短环。设满足该条件的边数为 z。若最短环唯一，其边集大小恰为 g，所以 z=g。若至少有两个最短环，它们的边集并集严格大于 g。此时 z>g，并且 h=g。

若 z=g，最短环唯一。任何其他环都至少有一条边不在这个最短环中；该边的 c_e 不超过该环长度。反过来，任意 c_e>g 都对应另一个环。因此，所有严格大于 g 的 c_e 的最小值就是 h。

下面统计达到最小值的删边方案。对每条非桥边 e=(x,y)，在删除 e 的图中分别从 x,y 进行 BFS。记距离为 d_x,d_y，并设：

D=d_x(y)=c_e-1

考虑另一条边 j=(u,v)。它属于某条最短 x\to y 路径，当且仅当下列两个方向至少有一个成立：

\begin{aligned} d_x(u)+1+d_y(v) & =D \\ d_x(v)+1+d_y(u) & =D \end{aligned}

所有满足条件的边组成最短路图。沿任意最短路前进时，d_x 每次恰好增加 1。因此，每条最短路都会在每一对相邻层之间选择恰好一条边。

同时，满足距离等式的每条边都至少属于一条最短路。因此，边 j 出现在所有最短绕路中，当且仅当它是所在层之间唯一的候选边。按层统计候选边数，就能确定所有必经关系，不需要路径计数或随机哈希。

用位集 must_e 记录 e 的所有最短绕路都必须经过哪些边。最后枚举无序边对 e,f。它能成为最优方案，当且仅当：

c_e+c_f-2=g+h-2

并且 f\notin must_e、e\notin must_f。这保证两条边各自都有一条避开另一条边的最短绕路，实际距离之和便等于全局下界。

此时剩余图也一定连通。因为两条被删边的端点都已经在剩余图中连通，把它们加回去不会合并任何连通块；而全部加回后是原连通图，所以剩余图只能有一个连通块。

每条边需要两次 BFS 和两次边扫描。时间复杂度为 O(m(n+m))，空间复杂度为 O(n+m+m^2/w)，其中 w 为机器字长。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=5005;
const int M=5005;
const int inf=0x3f3f3f3f;
struct Edge
{
    int u,v;
}e[M];
int n,m;
int d[2][N],cyc[M],lev[M],cnt[N];
vector<pii> g[N];
bitset<M> must[M];
void bfs(int s,int ban,int o)
{
    fill(d[o]+1,d[o]+n+1,-1);
    queue<int> q;
    d[o][s]=0;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto [y,id]:g[x])
        {
            if(id==ban||d[o][y]!=-1)continue;
            d[o][y]=d[o][x]+1;
            q.push(y);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)g[i].clear();
        for(int i=0;i<m;i++)
        {
            cin>>e[i].u>>e[i].v;
            g[e[i].u].push_back({e[i].v,i});
            g[e[i].v].push_back({e[i].u,i});
            must[i].reset();
        }
        for(int i=0;i<m;i++)
        {
            bfs(e[i].u,i,0);
            if(d[0][e[i].v]==-1)
            {
                cyc[i]=inf;
                continue;
            }
            bfs(e[i].v,i,1);
            cyc[i]=d[0][e[i].v]+1;
            fill(cnt,cnt+n,0);
            fill(lev,lev+m,-1);
            for(int j=0;j<m;j++)
            {
                if(j==i)continue;
                int x=e[j].u,y=e[j].v;
                if(d[0][x]+1+d[1][y]==cyc[i]-1)lev[j]=d[0][x];
                else if(d[0][y]+1+d[1][x]==cyc[i]-1)lev[j]=d[0][y];
                if(lev[j]!=-1)cnt[lev[j]]++;
            }
            for(int j=0;j<m;j++)
            {
                if(lev[j]!=-1&&cnt[lev[j]]==1)must[i][j]=1;
            }
        }
        int mn=inf;
        for(int i=0;i<m;i++)mn=min(mn,cyc[i]);
        int num=0,nxt=inf;
        for(int i=0;i<m;i++)
        {
            if(cyc[i]==mn)num++;
            else if(cyc[i]>mn)nxt=min(nxt,cyc[i]);
        }
        if(num>mn)nxt=mn;
        int sum=mn+nxt-2,ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=i+1;j<m;j++)
            {
                if(cyc[i]+cyc[j]-2==sum&&!must[i][j]&&!must[j][i])ans++;
            }
        }
        cout<<sum<<' '<<ans<<'\n';
    }
    return 0;
}