自动搬运

查看原文

来自洛谷，原作者为

	Fire_flame 乐观乐观再乐观

搬运于2025-08-24 22:51:03，当前版本为作者最后更新于2023-04-01 11:27:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathtt{Solution}$

其实题目描述是来迷惑你的（

因为每一次可以从任意已攻占的城市出发，所以相当于是求最小生成树。

我们可以用 bfs 马走日求出每两个点之间的边权。然后再跑一遍最小生成树即可。

但是 bfs 的时候，每一个点入队的时候就要标记为走过，如果等到遍历到这个点的时候再标记就晚了。

时间复杂度 $O(nm^2+m\log n)$（kruskal），$O(nm^2+n\log n)$（prim）。

标程一（bfs + kruskal）：

#include<bits/stdc++.h>//By Fire_flame
using namespace std;
const int MAXN = 3e3 + 5, MR = 9e6 + 5, MN = 2e2 + 5;
int n, m, cnt, ans, mp[MN][MN], f[MN][MN], fa[MAXN];
struct edge{
    int x, y, len;
    bool operator < (const edge &ll)const{
        return len < ll.len;
    }
}e[MR];
struct node{
    int x, y;
    bool operator < (const node &rr)const{
        if(x != rr.x)return x < rr.x;
        return y < rr.y;
    }
}a[MAXN];
struct step{
    int x, y, len;
};
int dx[] = {-1, 1, 2, -2, -1, 1, 2, -2};
int dy[] = {2, 2, 1, 1, -2, -2, -1, -1};
void bfs(int sx, int sy){
    queue<step>q;
    q.push({sx, sy, 0});
    memset(f, 0, sizeof(f));
    f[sx][sy] = 1;
    while(!q.empty()){
        int tx = q.front().x, ty = q.front().y, tl = q.front().len;
        q.pop();
        for(int i = 0;i < 8;i ++){
            int px = tx + dx[i], py = ty + dy[i];
            if(f[px][py] || px <= 0 || py <= 0 || px > m || py > m)continue;
            if(mp[px][py])e[++ cnt] = {mp[sx][sy], mp[px][py], tl + 1};
            f[px][py] = 1;
            q.push({px, py, tl + 1});
        }
//        printf("%d %d %d\n", tx, ty, tl);
    }
}
int find(int u){
    if(fa[u] == u)return u;
    return fa[u] = find(fa[u]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++)scanf("%d%d", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1);
    for(int i = 1;i <= n;i ++)mp[a[i].x][a[i].y] = fa[i] = i;
    for(int i = 1;i <= n;i ++)bfs(a[i].x, a[i].y);
    sort(e + 1, e + cnt + 1);
    for(int i = 1;i <= cnt;i ++){
        int tx = e[i].x, ty = e[i].y, tl = e[i].len;
        if(find(tx) != find(ty)){
            fa[find(tx)] = find(ty);
            ans += tl;
        }
    }
    printf("%d", ans + n - 1);
    return 0;
}

标程二（bfs + prim）：

#include <bits/stdc++.h>//代码提供者：康立扬
using namespace std;
int n;
int x,y,diss[310][310],u,v,vis[310][310],dis[4010],ans,N,a[310][310];
pair<int,int> q1[202500];int hd,tl;
struct node{
	int u,dis;
	bool operator<(const node &a) const{
		return dis>a.dis;
	}
};

int fx[8]={-1,1,2,-2,-1,1,2,-2};
int fy[8]={2,2,1,1,-2,-2,-1,-1};
struct point{
	int x,y;
}c[4010];
void bfs(int x,int y){
	hd=0,tl=0;
	q1[tl++]={x,y};
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) vis[i][j]=0;
	diss[x][y]=1;
    vis[x][y]=1;
    int cnt=1;
	while(hd<tl){
		pair<int,int>u=q1[hd++];
        //cout<<"~~"<<u.first<<" "<<u.second<<" "<<diss[u.first][u.second]<<"\n";
		if(cnt==n) break;
		for(int i=0;i<8;i++){
			pair<int,int>v={u.first+fx[i],u.second+fy[i]};
            //cout<<"to"<<v.first<<" "<<v.second<<"\n";
			if(vis[v.first][v.second]||v.first<1||v.second<1||v.first>N||v.second>N) continue;
			diss[v.first][v.second]=diss[u.first][u.second]+1;
		    vis[v.first][v.second]=1;
		    if(a[v.first][v.second]) cnt++;
			q1[tl++]=v;
		}
	} 
}
priority_queue<node>q;
void prim(){
    dis[0]=0;
	q.push({0,0});
	while(!q.empty()){
		int u=q.top().u,d=q.top().dis;
		q.pop();
		if(d!=dis[u]) continue;
		ans+=d;
		//cout<<u<<" "<<d<<"\n";
		dis[u]=0;
		bfs(c[u].x,c[u].y);
		for(int i=0;i<n;i++){
			if(diss[c[i].x][c[i].y]<dis[i]){
				dis[i]=diss[c[i].x][c[i].y];
				q.push({i,dis[i]});
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	memset(dis,0x3f,sizeof dis);
	scanf("%d",&N);
	for(int i=0;i<n;i++){
		scanf("%d%d",&u,&v);
		c[i].x=u,c[i].y=v;
		a[u][v]=1;
	}
	prim();
	printf("%d\n",ans);
	return 0;
}