题意
给一张图,要求你再尽可能的多连边,使得从1到2至少要经过5条边
没啥复杂的公式,讲解都在注释里
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
//P3505 [POI2010]TEL-Teleportation https://www.luogu.com.cn/problem/P3505
//bzoj2088 https://darkbzoj.tk/problem/2088
//题目的意思实际上就是,给出一张图,问最多能加几条边,使得 1->2 的最短路径长度,大于等于 5
//用一点分层图的思想
//考虑将图分成 5 层
//一层:点 1
//二层:和 1 相连的点
//五层:点 2
//四层:和 2 相连的点
//三层:剩下的点
//然后如何加边在代码的注释里,大体思路就是先考虑一层内的加边,然后再考虑层与层之间的
//最后再减去原有的边数,至于怎么严格证明这样是最优的并不会...
//type 表示的是所在层的编号
int type[40006];
int x[1000006],y[1000006];
int n,m;
int link[40006];//这个表示的是 3 层中的点与 2,4 哪一层相连,具体看下面的注释
inline void swap(int &x,int &y){x^=y;y^=x;x^=y;}
int main(){
n=read();m=read();
for(reg int i=3;i<=n;i++) type[i]=3;
type[1]=1;type[2]=5;
int edgenum_2=0,edgenum_3=0,edgenum_4=0;//两个端点均为某层的边的个数
int edgenum_23=0,edgenum_34=0;//两层之间的边数
for(reg int i=1;i<=m;i++){//先处理出各个点都在哪一层
x[i]=read();y[i]=read();
if(x[i]>y[i]) swap(x[i],y[i]);
if(x[i]==1) type[y[i]]=2;
else if(x[i]==2) type[y[i]]=4;
}
for(reg int i=1;i<=m;i++){//处理边数
if(type[x[i]]==2&&type[y[i]]==2) edgenum_2++;
else if(type[x[i]]==3&&type[y[i]]==3) edgenum_3++;
else if(type[x[i]]==4&&type[y[i]]==4) edgenum_4++;
else if((type[x[i]]==2&&type[y[i]]==3)||(type[x[i]]==3&&type[y[i]]==2)) edgenum_23++;
else if((type[x[i]]==4&&type[y[i]]==3)||(type[x[i]]==3&&type[y[i]]==4)) edgenum_34++;
}
int vertex_2=0,vertex_3=0,vertex_4=0;//处理各个层的点的个数
for(reg int i=1;i<=n;i++){
if(type[i]==2) vertex_2++;
else if(type[i]==3) vertex_3++;
else if(type[i]==4) vertex_4++;
}
int ans=0;
//先处理每层内部连边
ans+=vertex_2*(vertex_2-1)/2-edgenum_2;
ans+=vertex_4*(vertex_4-1)/2-edgenum_4;//2,4 层内的点能随便互相连,肯定不会使路径小于 5
//3 层内的点,我们要保证从 2 层走到 3 层后,不能立刻走到 4 层,否则就会出现长度为 4 的路径
//也就是说要有一步是从 3 层的点起步,然后终点也是 3 层的点
//那么,如果和 2 层的某个点相连,就不能和与 4 层的任何点相连,反之,和 4 相连不和 2 相连
//题目规定有解,所以并不会有点同时与 2,4 相连(在原有的边的情况下)
//那么我们可以考虑先处理出在第 3 层中,哪些点与 2 层中的点相连,哪些和 4 中的点相连
for(reg int i=1;i<=m;i++){
if(type[x[i]]==3){
if(type[y[i]]==4) link[x[i]]=4;
else if(type[y[i]]==2) link[x[i]]=2;
}
if(type[y[i]]==3){
if(type[x[i]]==4) link[y[i]]=4;
else if(type[x[i]]==2) link[y[i]]=2;
}
}
int link_2=0,link_4=0,link_no=0;//分别是:在第三层中,与第二层的点相连的点数,与第四层的点相连的点数,不与二或四层的点相连的点数
for(reg int i=1;i<=n;i++)if(type[i]==3){
if(link[i]==2) link_2++;
else if(link[i]==4) link_4++;
else link_no++;
}
ans+=link_no*(link_no-1)/2;//不与 2,4 相连的点随便连
//下面两行就是前面讲的,如果一个点和 2 层相连,那么它可以再与其余的在第三层,并且与 2 层相连的点相连,也可以和不与 2,4 层相连的点相连
//和 4 层相连的点也是同理
//这部分自己拿样例画画图比较好
ans+=link_2*(link_2-1)/2+link_2*link_no;
ans+=link_4*(link_4-1)/2+link_4*link_no;
ans+=link_2*link_4;//和 2 层相连的也可以与和 4 层相连的点随便连
ans-=edgenum_3;//去掉原有的,两个端点都在第 3 层的边数
/********************************************************************/
//下面是不同层之间的连边
//显然,不能跨过一层连边,那样肯定有小于 5 的路径,只能在相邻的层之间连
//1,2 层和 4,5 层肯定不会再有能连的边了
//对于第 3 层:
ans+=link_2*vertex_2-edgenum_23;//和 2 层相连接的点,可以和其它的 2 层的点都连起来,然后再减去 2,3 层之间的边去重
ans+=link_4*vertex_4-edgenum_34;//和 4 层相连的,同理
ans+=link_no*std::max(vertex_2,vertex_4);
//解释上一行:对于不和 2 或 4 层相连的点,只能和 2 或 4 层其中一层的所有点相连,为例最大化边数,肯定是都和 2,4 中点多的一层中的所有点链接
std::printf("%d",ans);
return 0;
}