题意

在保证 $1$ 号点到 $2$ 号点除原边外的最短路径边数 $\ge 5$ 的前提下，最多能添加多少条边。

分析

我们不难想到构造一个六层的分层图，将 $1$ 号点放在第一层，$2$ 号点放在第六层，并规定每一层的点只能与同一层或相邻的两层的点连边。那么就一定能保证 $1$ 号点到 $2$ 号点除原边外的最短路径边数 $\ge 5$。

根据我们的规定，将与 $1$ 号点相连的点放在第二层，与 $2$ 号点相连的点放在第五层，以此类推。若在第一次分层后还有点不在分层图中，那么就根据第二层和第五层的点数来决定将这些点放在第三层还是第四层。因为无论这些点放在第三层还是第四层对于对方的贡献相同，对于本层的贡献无论怎么分配在满足规定的连满的情况下总和不变，只要考虑放第三层与第二层连边的贡献和放第四层与第五层连边的贡献那个大就行了。

因为要在满足要求的前提下尽可能多加边，所以我们贪心地将每一层的点与同一层和相邻的两层的点都连边。

具体的，我们设 $cnt_i$ 为第 $i$ 层的点数。则总边数为

$$E_{max} = \sum_{i=1}^{5} (cnt_i \times cnt_{i+1}) + \sum_{i=2}^{5} \frac{cnt_i \times (cnt_i-1)}{2}$$

因为我们要求的是新加的边数，所以答案减去原边数即可。

即：

$$ans=E_{max}-m$$

实现

::::info[如果你学会了就补药打开]

#if __cplusplus == 202302L
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int maxm=1e5+10;
const int INF=1e9;
const double PI=acos(-1);
int __n__,__m_,__T,___aaa___,__bulitin_popconut,l191ubq,tmp;
vector<int>c_n_t(maxn);
vector<int>__d__(maxn);
array<vector<int>,maxn>__gra__;
signed main(){
    cin>>__n__>>__m_;
    for(int i=1,u,v;i<=__m_;++i){
        cin>>u>>v;
        __gra__[u].emplace_back(v);
        __gra__[v].emplace_back(u);
    }
    __d__[1]=1;
    ++c_n_t[1];
    __d__[2]=6;
    ++c_n_t[6];
    for(int v:__gra__[1]) __d__[v]=2,++c_n_t[2];
    for(int v:__gra__[2]) __d__[v]=5,++c_n_t[5];
    for(int i=1;i<=__n__;++i)
    {
        if(__d__[i]==2){
            for(int v:__gra__[i]){
                if(!__d__[v])__d__[v]=3,++c_n_t[3];
                }
        }if(__d__[i]==5){
            for(int v:__gra__[i]){
                if(!__d__[v])__d__[v]=4,++c_n_t[4];
                }}}
    for(int i=1;i<=__n__;++i){
        if(!__d__[i]){
            if(c_n_t[2]>c_n_t[5])++c_n_t[3];
            else++c_n_t[4];
            }}
    for(int i=1;i<=5;++i){
        __bulitin_popconut+=c_n_t[i]*c_n_t[i+1];}
    for(int i=2;i<=5;++i){
        __bulitin_popconut+=c_n_t[i]*(c_n_t[i]-1)/2;}
    __bulitin_popconut-=__m_;
    cout<<__bulitin_popconut;
    while(true)if(clock()>=990700)return 0;
}
#else
#error "Don't copy TJ or You are a xxs"
signed main(){
    return 0;
}
#endif

AC记录 ::::