专栏文章

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

RRigel
P13489题解参与者 12已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@minsp42t
此快照首次捕获于
2025/12/02 07:43
3 个月前
此快照最后确认于
2025/12/02 07:43
3 个月前
查看原文

0x00

前情提要。
⋯\cdots 故总复杂度为 O(T(NM)2log⁡(NM))\mathcal{O}(T(NM)^2 \log(NM))。
Submission，最大点跑了 320320 ms，而时限为 33 s，很合理。
然后笔者点开了两位大神的提交记录，最大点分别为 1212 ms 和 55 ms。
在笔者的代码实现中，直接跑 N×MN \times M 轮 Dijkstra 求出了任意两点之间的距离。这样很直接，但也很暴力。许多点之间的距离没有必要求出。
回到初始的思路。
我们需要求出：
  • 连通所有普通岛屿的费用，即所有普通岛屿到离它最近的森林的距离。
  • 连通所有森林的费用。

0x01

以下是笔者与 Asedwai大神的交流。
注意到计算连通所有森林的费用只需要用到森林之间的距离。也就是说只要求出任意森林到其他所有点的距离即可。
从每个森林分别开始跑 BFS，共 CC 轮。时间复杂度为 O(TNMC)\mathcal{O}(TNMC)，即 O(T(NM)2)\mathcal{O}(T(NM)^2)。

0x02

以下是笔者与 AFewSuns大神的交流。
从所有森林出发，跑多源 BFS，记录所有岛屿离它最近的森林的距离以及离它最近的森林（记为它所属的森林）编号。
注意森林也算岛屿，它所属的森林即为本身。
遍历图中的每一个岛屿，检查它周围是否有所属森林编号不一样的岛屿。
若有，则在对应的森林之间加边。
开 N×MN \times M 个 vector 存边。存边数组的第一维代表原始边权，即边两端森林之间的距离。
加边的时候在对应边权的 vector 中 push_back 边两端森林编号。
时间复杂度瓶颈在于最后的 MST。将并查集的复杂度近似看作常数，则总复杂度为 O(TNM)\mathcal{O}(TNM)。

0x03

Code。
CPP
#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={d24+d2dmod  2=0,(d+1)(⌊d2⌋+1)2dmod  2=1.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}
其中 ww 为额外费用，dd 为森林之间的距离。公式的推导过程可见此处。

0xFF

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...