CF1776J Italian Data Centers 题解

· · 题解

只是一道几何分析加全源最短路。

首先，考虑对单个点的分裂状态。

将一个点分裂后的第一个点记为该点的 0 号，第二个点为 1 号。

则 k 天后一个点 u，会分裂出 2^{k} 个点。设 s 为 t 天后的某个状态，对 t+1 天，新分裂的 u_{\overline{s0}} 与 u_{\overline{s1}} 会连一条边。再分裂，u_{\overline{s00}} 与 u_{\overline{s01}} 连边，u_{\overline{s10}} 与 u_{\overline{s11}} 连边。

可以发现，两个点的状态标号在只有其中某一位上不同时，才会连边。这实际上是一个 k 维超立方体。

建议参考这篇

一个超立方体上可以被经过的最长的最短路长为 k，因为每移动到相邻的点上，至多能改变一个二进制位。从向量 (x_1,x_2,\cdots,x_k) 至 (1-x_1,1-x_2,\cdots,1-x_k) 最短路最长，恰为 k。

其次，考虑两个超立方体之间的连边。

由于是最短路，在单个超立方体上的移动至多进行一次，最大为 k，相当于跨越了一半的超立方体。因此一个点可以简化为 0,1 两个状态，两点互相对顶（最长的最短路在单个超立方体上一定移动了最多）。

对于连边：颜色相同的超立方体在每次二进制位延展（从第 k 至第 k+1 天）时，会把两个超立方体延展的那位相等的两个顶点连边，因此只有两点最终状态相同（初始就两个 0 维原点，类似数学归纳法）时相连。反之，颜色不同就只有两点最终状态互补时相连。

一个点简化为了两个状态，可以用 floyed 求出各个点两两之间的最短路。

寻找最长的最短路，可以先找最长的最短环，再破为两半。固定一个顶点 u，对于超立方体 v，其中最长环为三段：从 u 分别到 v 上两对顶点的两端距离，及两对顶点间的距离。前两段距离由 floyed 求出，最后的那段最优取 k。

代码：

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

const int range=605;

const int lim=0x3f3f3f3f;

int n,m,k;

int c[range];

int grab[range][range],ans;

inline int get(int u,bool op)
{
    return op*n+u;
}

int main()
{
    memset(grab,lim,sizeof(grab));

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        grab[i][i]=grab[get(i,1)][get(i,1)]=0;
        grab[get(i,1)][i]=grab[i][get(i,1)]=k;
    }

    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(c[u]==c[v]) 
        {
            grab[get(u,0)][get(v,0)]=grab[get(v,0)][get(u,0)]=1;
            grab[get(u,1)][get(v,1)]=grab[get(v,1)][get(u,1)]=1;
        }
        else
        {
            grab[get(u,0)][get(v,1)]=grab[get(v,0)][get(u,1)]=1;
            grab[get(u,1)][get(v,0)]=grab[get(v,1)][get(u,0)]=1;
        }
    }

    int ran=2*n;

    for(int kk=1;kk<=ran;kk++)
    {
        for(int i=1;i<=ran;i++)
        {
            for(int j=i+1;j<=ran;j++)
            {
                grab[j][i]=grab[i][j]=min(grab[i][j],grab[i][kk]+grab[kk][j]);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ans=max(ans,(grab[i][get(j,0)]+grab[i][get(j,1)]+k)/2);
        }
    }

    printf("%d",ans);

    return 0;
}