[KMOI R1] 军事行动题解

· · 题解

\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;
}