如何将 O(T(NM)^2 log(NM)) 优化至 O(TNM)？

· · 题解

0x00

前情提要。

Submission，最大点跑了 320 ms，而时限为 3 s，很合理。

然后笔者点开了两位大神的提交记录，最大点分别为 12 ms 和 5 ms。

在笔者的代码实现中，直接跑 N \times M 轮 Dijkstra 求出了任意两点之间的距离。这样很直接，但也很暴力。许多点之间的距离没有必要求出。

回到初始的思路。

我们需要求出：

0x01

以下是笔者与 @Asedwai 大神的交流。

注意到计算连通所有森林的费用只需要用到森林之间的距离。也就是说只要求出任意森林到其他所有点的距离即可。

从每个森林分别开始跑 BFS，共 C 轮。时间复杂度为 \mathcal{O}(TNMC)，即 \mathcal{O}(T(NM)^2)。

0x02

以下是笔者与 @AFewSuns 大神的交流。

从所有森林出发，跑多源 BFS，记录所有岛屿离它最近的森林的距离以及离它最近的森林（记为它所属的森林）编号。

注意森林也算岛屿，它所属的森林即为本身。

遍历图中的每一个岛屿，检查它周围是否有所属森林编号不一样的岛屿。

若有，则在对应的森林之间加边。

开 N \times M 个 vector 存边。存边数组的第一维代表原始边权，即边两端森林之间的距离。

加边的时候在对应边权的 vector 中 push_back 边两端森林编号。

时间复杂度瓶颈在于最后的 MST。将并查集的复杂度近似看作常数，则总复杂度为 \mathcal{O}(TNM)。

0x03

Code。

#include<bits/stdc++.h>
#define int long long

const int N=35; 

using namespace std;

const int f[4][2]={{-1,0},{0,-1},{1,0},{0,1}};

int T,n,m,tim,tot,cnt,fa[N*N],siz[N*N],id[N][N],dis[N][N],vis[N][N],bel[N][N],ans;

char c[N][N];

vector<pair<int,int> >t[N*N];

struct node{
    int x,y,stp,k;
}q[N*N];

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

inline char read1(){ // 更为保险的字符读入 
    char ch=getchar();
    while(ch!='T'&&ch!='#'&&ch!='.')ch=getchar();
    return ch;
}

void _init(){ // 多测不清空，____ 两行泪 
    tim++;
    tot=cnt=ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            id[i][j]=(i-1)*m+j; // 给每个点编号 
            dis[i][j]=vis[i][j]=bel[i][j]=0;
        }
    }
    for(int i=1;i<=n*m;i++)fa[i]=i,siz[i]=1,t[i].clear();
}

bool chk(int i,int j){
    if(i<1||j<1||i>n||j>m)return 0;
    return c[i][j]!='.';
}

void BFS(){
    int hed=0,til=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[i][j]=='T'){
                tot++;
                vis[i][j]=1;
                bel[i][j]=id[i][j];
                q[++til]=(node){i,j,0,id[i][j]};
            }
        }
    }
    while(hed^til){
        hed++;
        int x=q[hed].x,y=q[hed].y,stp=q[hed].stp,_k=q[hed].k;
        for(int i=0;i^4;i++){
            int _x=x+f[i][0],_y=y+f[i][1];
            if((!chk(_x,_y))||vis[_x][_y])continue;
            q[++til]=(node){_x,_y,stp+1,_k};
            dis[_x][_y]=stp+1; // 记录该岛屿与离它最近的森林的距离 
            vis[_x][_y]=1;
            bel[_x][_y]=_k; // 记录离该岛屿最近的森林编号 
        }
    }
}

int _calc(int d){ // 计算额外费用 
    if(d&1)return (d+1)*((d/2)+1)/2;
    return d*d/4+d/2;
}

int getfa(int x){
    return (fa[x]==x)?x:(fa[x]=getfa(fa[x]));
}

void _uni(int x,int y){
    if(siz[x]>siz[y])swap(x,y);
    fa[x]=y;
    siz[y]+=siz[x];
}

void _solve(){
    n=read(),m=read();
    _init();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c[i][j]=read1();
    BFS(); // 从所有森林开始跑多源 BFS 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[i][j]=='.')continue;
            ans+=dis[i][j]; // 普通岛屿与离它最近的森林的距离即为连通这个岛屿的费用 
            for(int k=0;k^4;k++){
                int x=i+f[k][0],y=j+f[k][1];
                if((!chk(x,y))||bel[i][j]==bel[x][y])continue;
                int d=dis[i][j]+dis[x][y]+1; // 注意此处要 +1 
                t[d].push_back(make_pair(bel[i][j],bel[x][y])); // 加边 
            }
        }
    }
    for(int i=1;i<=n*m;i++){ // i 为原始边权 
        for(int j=0;j^t[i].size();j++){
            int u=t[i][j].first,v=t[i][j].second,w=_calc(i); // w 为实际所需的额外费用 
            int fx=getfa(u),fy=getfa(v);
            if(fx==fy)continue;
            _uni(fx,fy);
            ans+=w;
            cnt++;
            if(cnt==tot-1)break;
        }
    }
    printf("Case #%lld: %lld\n",tim,ans);
}

signed main(){
    T=read();
    while(T--)_solve();
    return 0;
}

Submission，速度快到飞起。

计算森林相连的额外费用的公式：

w = \begin{cases} \dfrac{d^2}{4} + \dfrac{d}{2} & d \mod 2 = 0,\\ \\ \dfrac{(d+1)(\lfloor \dfrac{d}{2} \rfloor + 1)}{2} & d \mod 2 = 1. \end{cases}

其中 w 为额外费用，d 为森林之间的距离。公式的推导过程可见此处。

0xFF