P3505 [POI2010]TEL-Teleportation 题解

· · 题解

\text{Update : 最后分配点的正确性证明。}

解题思路：

将整个图分成有顺序的 6 个部分，每一部分只和相邻的两个（端点只有一个）部分相连，这样从第一个部分到第六个部分一定要经过至少 5 条边，也就是题目条件。

将第一个点放在第一个部分，与第一个点直接相连的部分放在第二个部分，与第二个部分有连边的放在第三个部分。再将第二个点放在第六个部分，与第二个点直接相连的放在第五个部分，与第五个部分有连边的放在第四个部分。都不满足的先放一边。

然后对于每一个部分的内部，一定可以任意连边，这一部分的价值可以直接统计。相邻的两个部分之间也可以直接连边，代价也可以直接算出来。

最后将那些都不满足的边放到中间两个部分中能产生最大价值的就行了。

注意题目要求的是增加的边的数量，需要减去原有的边数 m。

最后一步分配剩余的点的正确性证明：

先考虑只有一个点的情况。不妨设第二部分到第五部分的点的数量分别为 a，b，c，d，这个点之前就有的连边一共有 u 条。

然后分情况讨论，将这个点放在第一到第五个部分能产生的价值分别是：a+b+1-u，a+b+c-u，b+c+d-u 和 c+d+1-u，由于题目中保证 1 和 2 两个点联通，所以 b,c\ge 1。由此得出一定放在中间两个部分，且取 a 和 d 中较大的一个的相邻位置（这个点可能和中间两个位置中的一个有连边，此时不能放在与连边部分相对的位置，但是即使能放也不可能产生更大的价值，所以可以不用考虑）。

由此拓展到多个点，由之前一个点的推导，这样的一些点一定是放在中间两个部分中的一个，所以不妨设总共有 t 个可以任意放置的点，放在第三个部分的点有 x 个，则放在第四个部分的点有 t-x 个，沿用之前每一个部分点的数量。

此时可以将产生的总价值表示为 \dfrac{t(t+1)}{2}+x(a+b+c)+(t-x)(b+c+d)，变形得到 \dfrac{t(t+1)}{2}+t(b+c+d)+x(a-d)，其中变化的只有 x。

这是一个 x 的一次式，求导之后的结果为定值 a-d，最大值一定取在端点处，也就是一定在 x=0 或者 x=t 处取最大，具体取决于 a-d 和 0 的大小关系。换句话说，要不然全都放在第三个部分，要不然就全都放在第四个部分，也就是之前得到的结论。

代码：

#include<cstdio>
using namespace std;
#define int long long
const int MAXN=4000005;
int n,m,head[MAXN],nxt[MAXN],num[MAXN],x,y,cnt,col[MAXN],cnt2,cnt5,cnt3,cnt4,ans;
void add(int x,int y){
    nxt[++cnt]=head[x];head[x]=cnt;num[cnt]=y;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    col[1]=1;col[2]=6;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=head[1];i;i=nxt[i]){
        col[num[i]]=2;cnt2++;
    }
    for(int i=head[2];i;i=nxt[i]){
        col[num[i]]=5;cnt5++;
    }
    for(int i=1;i<=n;i++){
        if(col[i]==2){
            for(int j=head[i];j;j=nxt[j])
            if(col[num[j]]==0)col[num[j]]=3,cnt3++;
        }
        if(col[i]==5){
            for(int j=head[i];j;j=nxt[j])
            if(col[num[j]]==0)col[num[j]]=4,cnt4++;
        }
    }
    for(int i=1;i<=n;i++)
    if(col[i]==0){
        if(cnt2>cnt5)cnt3++;
        else cnt4++;
    }
    ans=cnt2+cnt5+cnt2*(cnt2-1)/2+cnt3*(cnt3-1)/2+cnt4*(cnt4-1)/2+cnt5*(cnt5-1)/2
    +cnt2*cnt3+cnt3*cnt4+cnt4*cnt5-m;
    printf("%lld\n",ans);
    return 0;
}