题解

分类讨论

所有边（除 $1\text{-}2$ 之间那条 250min 的边）都长 1h，若新增一条边 $(u,v)$，通过该边产生的最短路长度为

$$\min\{\operatorname{dist}_1(u) + 1 + \operatorname{dist}_2(v),\ \operatorname{dist}_1(v) + 1 + \operatorname{dist}_2(u)\}. $$

题意要求最短路仍为 250min（即 $>4$ 条边），因此我们只需关心距 1、2 号点不超过 2 条边的顶点。用两次 BFS（都只跑到深度 2）即可把所有顶点划分成下列 6 个集合：

标号	含义
1	节点 1 本身（dist$_1=0$）
2	dist$_1=1$ 的点
3	dist$_1=2$ 的点
4	dist$_2=2$ 的点（且 dist$_1\ge 3$）
5	dist$_2=1$ 的点（且 dist$_1\ge 3$）
6	节点 2 本身
0	其余点（dist$_1,dist_2\ge 3$）

由于原图中 $1$ 到 $2$ 的所有路径都不少于 5 条边，因此绝不会出现既在左侧又在右侧“近邻”集合中的点。

允许加入的边

• 同一集合内部：任意两点之间新增的边都不会把 $1\text{-}2$ 最短路降到 4 内（因为它们离另一端至少 3 条边），共贡献 $\sum_{i=1}^6 \binom{sz_i}{2}$；
• 相邻集合之间：沿着“1 的一侧：1→2→3，2 的一侧：4→5→6”的顺序，只要两个集合在这个序列里相邻，就可以自由连边，总数 $\sum_{i=1}^5 sz_i \cdot sz_{i+1}$；
• 远离两端的点（集合 0）：彼此之间随便连边，贡献 $\binom{sz_0}{2}$；它们还可以和集合 3、4 的点全部相连，因为无论怎么经过都会至少 5 条边；
• 远点与集合 2/5：若同一个远点同时接上集合 2 与集合 5，就会出现长度恰好 4 的新路径（1→集2→远点→集5→2）。因此每个远点最多只能选择其中一侧相连，我们取更优的一侧，总贡献为 $sz_0 \cdot \max(sz_2, sz_5)$；
• 远点与集合 3/4：二者都离另外一端至少 3 条边，所以可以全部连接，贡献 $sz_0 \cdot (sz_3 + sz_4)$。

把以上几类边全部相加即可得到“最多允许存在的边数”，再减去原图已有的 $m$ 条边，答案就是仍然可以新增的最大边数。

复杂度

两次 BFS 的开销为 $O(n+m)$，后续全是按集合大小做组合数和乘法，时间、空间都为 $O(n)$。

参考代码

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

const int N = 4e5 + 10;

int n, m, sz[N], d[N], vis[N];

vector<int> e[N];

void read(){
	cin >> n >> m;
	for(int i = 1;i <= m; i++){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
}

void init(){

}

void bfs1(){
	queue<int> q;
	q.push(1);
	d[1] = 1;
	while(q.size()){
		int u = q.front(); q.pop();
		for(int v : e[u]){
			if(d[v]) continue;
			d[v] = d[u] + 1;
			if(d[v] < 3) q.push(v);
		}
	}
}

void bfs2(){
	queue<int> q;
	q.push(2);
	d[2] = 6;
	while(q.size()){
		int u = q.front(); q.pop();
		for(int v : e[u]){
			if(d[v]) continue;
			d[v] = d[u] - 1;
			if(d[v] > 4) q.push(v);
		}
	}
}

void compute(){
	bfs1(); bfs2();
	for(int i = 1;i <= n; i++) {
//		cout << i << ':' << d[i] << '\n';
		sz[d[i]]++;
	}
	int ans = 0, sum = 0;
	for(int i = 1;i <= 6; i++){
		ans += sz[i] * (sz[i] - 1) / 2;
		sum += sz[i];
	}
	for(int i = 1;i < 6; i++){
		ans += sz[i] * sz[i+1];
	}
	sum = n - sum;
	ans += sum * (sum - 1) / 2;
	ans += sum * (sz[4] + sz[3] + max(sz[2],sz[5]));
	cout << ans - m;
}

void fre(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int main(){
//	fre("");
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read(); init(); compute();
	return 0;
}