G7017 [GESP202512 七级] 城市规划 题解

知识点：广度优先搜索、图的中心、最值。

解题思路

对每个候选城市做BFS，求到其他城市的最大最短路距离，选该值最小者，并在平局时保留较小编号。

为什么正确

BFS计算无权图的正确最短路，最大距离是该候选的最坏服务范围，逐候选取最小得到图中心。

易错点

题目图连通；平局不能用<=更新，否则会覆盖成更大编号。

复杂度

时间O(n(n+m))，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>g(n+1);
    while(m--) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int best=n+1,ans=1;
    for(int s=1;s<=n;s++) {
        vector<int>d(n+1,-1),q= {
            s
        }
        ;
        d[s]=0;
        int mx=0;
        for(int k=0;k<(int)q.size();k++)for(int v:g[q[k]])if(d[v]<0) {
            d[v]=d[q[k]]+1;
            mx=max(mx,d[v]);
            q.push_back(v);
        }
        if(mx<best) {
            best=mx;
            ans=s;
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。