题意

在给定的无向图中添加尽可能多的边，需要满足 $1$ 号点到 $2$ 号点的距离为 $5$。

做法

首先我们把点分成两类，一类是 $1$ 到 $2$ 最短路之间的点，另一类是不在 $1$，$2$ 最短路之间的点。

然后我们考虑如何连边。先考虑第一类点，这一类点到 $1$ 的距离为 $[0,5]$，我们使用 $cnt[i]$ 表示第一类点中，距离 $1$ 号点为 $i$ 的点的个数。

然后我们连边，这一类点在连边时，对于每个距离 $i$，只有两种方式。

1. $cnt[i]$ 个点两两连边。
2. $cnt[i]$ 个点向 $cnt[i+1]$ 个点连边。

这样连边，不会影响任何一个点到 $1$ 和到 $2$ 的距离。如果连了别的边，一定会导致最短路变短。

然后是第二类点。这一类点，它们自己之间可以两两连边。然后也可以向第一类点连边，但连完之后要满足不会影响最短路长度，所以连向的点的数量为 $\max_{i=2}^3 cnt[i-1]+cnt[i]+cnt[i+1]$，这是因为第一类点到第二类点，一个来回距离为 $2$，所以最多是三个相邻的。如果再远了，就可以从 $1$ 号点经过第二类点，再走到 $2$ 号点来缩短最短路长度，不符合条件。而且如果连向中间的 $cnt[2]$ 或 $cnt[3]$，显然会更优，因为 $cnt[0]=cnt[5]=1$。而且如果你往 $cnt[1]$ 或 $cnt[5]$ 连边，可能会不合法。

比如现在有一个第二类点，已经向 $cnt[4]$ 中的一个点连边了，就不能再和 $cnt[0]$ 中的点连边了。所以令 $i=2$ 或 $i=3$ 即可，这样不仅合法还会更优。

然后把两个加起来就行，然后要减去 $m$，因为题目不允许重边。

代码

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0;
	char e=getchar();
	while(e<'0'||e>'9') {
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x;
}
const int N=400005,M=2000005;
int head[N],ver[M],nxt[M],idx=-1;
void add(int x,int y) {
	++idx;
	ver[idx]=y;
	nxt[idx]=head[x];
	head[x]=idx;
}
int dis[N],vis[N];
int n,m,ans;
int cnt[10],w;
bool vi[N];
void bfs(int s) {
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[s]=0;
	vis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		if(dis[u]<=2&&vi[u]==0){
			if(s==1)cnt[dis[u]]++;
			else cnt[5-dis[u]]++;
			vi[u]=1;
		}
		for(int i=head[u]; ~i; i=nxt[i]) {
			int v=ver[i];
			if(vis[v])continue;
			vis[v]=1;
			dis[v]=dis[u]+1;
			q.push(v);
		}
	}
}
signed main() {
//	freopen("ex.in","r",stdin);
//	freopen("out.txt","w",stdout);
	memset(head,-1,sizeof head);
	R(n),R(m);
	for(int i=1; i<=m; ++i) {
		int R(u),R(v);
		add(u,v),add(v,u);
	}
	bfs(1);
	bfs(2);
	for(int i=1;i<=n;++i){
		if(!vi[i])++w;
	}
	int mx=0,sum=-m;
	for(int i=1;i<=4;++i){
		mx=max(mx,cnt[i]+cnt[i-1]+cnt[i+1]);
	}
	for(int i=0;i<=5;++i){
		sum+=cnt[i]*(cnt[i]-1)/2+cnt[i]*cnt[i+1]; 
//		cout<<cnt[i]<<" ";
	} 
//	cout<<w<<"\n";
	sum+=mx*w+w*(w-1)/2;
	cout<<sum<<"\n";
	return 0;
}

吃饭路上也要锻炼 题解

这里是分五层做法↓↓↓!!!

从两头开始往中间“夹”：农场1是第一层，农场2是第五层；与农场1有一条边相连的农场们是第二层，与农场2有一条边相连的农场们是第四层。剩下的都“堆”成第三层。

考虑答案的合法性和最大化两点。

如果一条直线从第一层穿到第五层只能出现四条路径，不合法。如果像这样一层一层紧接着连下来都不合法，且保证设计出的最短路已存在5，那么跨层连是必不合法的。

什么时候会出现上述第一种“穿串”的情况？第三层存在一点与二四层都有连边。这种情况在已设计好的路线中是不可能存在的，所以我们在建新路时避免即可。

同层的点可连线以优化答案。

第三层与第二层有连边的点去和第二层的所有点连一遍，第三层与第四层有连边的点去和第四层的所有点连一遍。没有如上连边的点连第二层所有点或第四层所有点均可，不过肯定是选点更多的一侧来连。

记得去重！！！