题目描述

Description

Zy大帝拥有n个星球，因为距离非常遥远，所以Zy在他所居住的1号星球和他的军事基地霸中所在的2号星球建造了两个传送门，这样从1号星球到2号星球就只需要250分钟，回去也一样（双向）。由于科技的发展，各个星球陆陆续续建造了和自己居民最经常去的星球之间的传送门，并且他们的传送门只需要1个小时（真快啊！），他们发现和别的星球建设传送门对促进经济发展有很大的帮助，于是向和其他所有星球建设传送门发展，Zy突然发现两两星球的传送门的建设会威胁到他的安全，可是他又想促进自己帝国的发展，于是他请到了他精心培养的你，希望你能帮他解决这个难题。

Input

输入：第一行为两个由空格隔开的整数n（2<=n<=40000）和m(0<=m<=1000000)，n表示星球数，m表示其他星球已经建造的传送门的对数（传送门都是两两建造的）（不包括Zy在1号和2号的）。接下来m行每行两个由空格隔开的整数想x，y（2<=x,y<=40000），表示这两个星球建造了传送门连接。

Output

输出：还能让多少对传送门建造，但又不会比Zy从1号星球到2号星球快（就是说增加传送门后，从1号星球到2号星球还是Zy的传送门最快）。

Sample Input

10 10
1 3
3 5
5 7
7 9
2 9
1 4
4 6
6 8
8 10
2 10

Sample Output

10

实线连接的是已经造好传送门的两星球，虚线连接表示可以增加建造的传送门两星球。
可以看出，建造了10对以后，从1号到2号星球还是Zy的250分钟最快。

题目分析

抄一下题解:

把样例换个方式画出来 就会发现
->->
每一层都代表着该点最短到1和2的距离。有以下结论：

显然除了1,2外，其他点都会被分进这4层里。那么与1相连的，到1的最短距离为2的点只能放在1,2层；与2相连的，到2的最短距离为2的点只能放在4,3层。
对于在某一层的点，它只能和本层与相邻层的点连线，如果跨过一层连线，就会导致1,2的最短距离不是5了。
其他剩余没有被扔进图里的点，将其视作第2,3层中某层的点。这样首先是不会违背题意的，而且也更优：

如果扔进第1层，那么其增加的边个数是size1+1+size2。
如果扔进第2层，那么其增加的边个数是size1+size2+size3。
显然size3≥1，所以扔进中间两层更优。

显然增加的数值只会跟每层实际存在的点的个数有关，故可以枚举有多少点进入2层，多少点进入3层，再计算即可。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int head[40010],to[2000010],net[2000010];
int id[40010],cnt[40010];
int n,m,num,ans,tot;
void add(int x,int y){ net[++tot]=head[x],head[x]=tot,to[tot]=y; }
int calc()
{
    return cnt[1]+cnt[1]*(cnt[1]-1)/2+cnt[1]*cnt[2]+cnt[2]*(cnt[2]-1)/2+cnt[2]*cnt[3]+cnt[3]*(cnt[3]-1)/2+cnt[3]*cnt[4]+cnt[4]*(cnt[4]-1)/2+cnt[4];
}
void work()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    id[1]=5,id[2]=6;
    for(int i=head[1];i;i=net[i]) id[to[i]]=1,cnt[1]++;
    for(int i=head[2];i;i=net[i]) id[to[i]]=4,cnt[4]++;
    for(int i=1;i<=n;i++)
        if(id[i]==1)
        {
            for(int j=head[i];j;j=net[j])
                if(!id[to[j]]) id[to[j]]=2,cnt[2]++;
        }
        else if(id[i]==4)
        {
            for(int j=head[i];j;j=net[j])
                if(!id[to[j]]) id[to[j]]=3,cnt[3]++;
        }
    for(int i=1;i<=n;i++) if(!id[i]) num++;
    for(int i=0;i<=num;i++)
    {
        cnt[2]+=i,cnt[3]+=(num-i);
        ans=max(ans,calc());
        cnt[2]-=i,cnt[3]-=(num-i);
    }
    printf("%d",ans-m);
}
int main()
{
    work();
    return 0;
}