简答题 偏难
#19781

城市规划 题目描述 A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤…

城市规划

题目描述

A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤i≤m)条双向道路连接城市ui与城市vi。

对于城市u和城市v而言,它们之间的连通度d(u,v)定义为从城市u出发到达城市 所需经过的双向道路的最少条数。由于道路是双向的,可以知道连通度满足d(u,v)=d(v,u),特殊地有d(u,u)=0。

现在 A 国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市,如果有多个满足条件的城市,则选取其中编号最小的城市。形式化地,你需要求出使得max1≤i≤nd(u,i)最小的u,若存在多个可能的u则选取其中最小的。

输入格式

第一行,两个正整数n,m,表示 A 国的城市数量与双向道路数量。

接下来m行,每行两个整数ui,vi,表示一条连接城市ui与城市vi的双向道路。

输出格式

输出一行,一个整数,表示建设难度最小的城市编号。如果有多个满足条件的城市,则选取其中编号最小的城市。

输入样例 1

3 3
1 2
1 3
2 3

输出样例 1

1

输入样例 2

4 4
1 2
2 3
3 4
2 4

输出样例 2

2

数据范围

对于40的测试点,保证1≤n≤300 。

对于所有测试点,保证1≤n≤2000,1≤m≤2000,1≤ui,vi≤n。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; const int N = 2005; int n, m; vector&lt;int&gt; e[N]; int d[N], mx[N], q[N]; void bfs(int u) {     for (int i = 1; i &lt;= n; i++)         d[i] = n + 1;     d[u] = 0;     q[1] = u;     int ql = 1, qr = 1;     while (ql &lt;= qr) {         int x = q[ql++];         for (auto y : e[x])             if (d[x] + 1 &lt; d[y]) {                 d[y] = d[x] + 1;                 q[++qr] = y;             }     }     mx[u] = d[q[qr]]; } int main() {     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= m; i++) {         int u, v;         scanf("%d%d", &amp;u, &amp;v);         e[u].emplace_back(v);         e[v].emplace_back(u);     }     int ans = 1;     for (int i = 1; i &lt;= n; i++) {         bfs(i);         if (mx[i] &lt; mx[ans])             ans = i;     }     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。