简答题 偏难
#22100

day1-3 传统型

day1-3 传统型


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; #include &lt;algorithm&gt; using namespace std; const int MAXN = 2010; vector&lt;int&gt; adj[MAXN]; int pos[MAXN];      // 数字i的初始节点 int ans[MAXN];      // 数字i的最终节点 int parent[MAXN];   // BFS中记录父节点 // 查找从u到v的路径(节点序列,不包含u,包含v) vector&lt;int&gt; findPath(int u, int v, int n) {     fill(parent, parent + n + 1, -1);     queue&lt;int&gt; q;     q.push(u);     parent[u] = 0;     while (!q.empty()) {         int cur = q.front();         q.pop();         if (cur == v) break;         for (int neighbor : adj[cur]) {             if (parent[neighbor] == -1) {                 parent[neighbor] = cur;                 q.push(neighbor);             }         }     }     vector&lt;int&gt; path;     int cur = v;     while (parent[cur] != 0) {         path.push_back(cur);         cur = parent[cur];     }     reverse(path.begin(), path.end());     return path; } // 查找u所在连通块中的最小节点 int findMinNode(int u, int n) {     vector&lt;bool&gt; visited(n + 1, false);     queue&lt;int&gt; q;     q.push(u);     visited[u] = true;     int minNode = u;     while (!q.empty()) {         int cur = q.front();         q.pop();         if (cur &lt; minNode) minNode = cur;         for (int neighbor : adj[cur]) {             if (!visited[neighbor]) {                 visited[neighbor] = true;                 q.push(neighbor);             }         }     }     return minNode; } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     int T;     cin &gt;&gt; T;     while (T--) {         int n;         cin &gt;&gt; n;         for (int i = 1; i &lt;= n; ++i) {             cin &gt;&gt; pos[i];             ans[i] = pos[i];             adj[i].clear();         }         for (int i = 0; i &lt; n - 1; ++i) {             int x, y;             cin &gt;&gt; x &gt;&gt; y;             adj[x].push_back(y);             adj[y].push_back(x);         }         for (int i = 1; i &lt;= n; ++i) {             int u = ans[i];             int minNode = findMinNode(u, n);             if (u == minNode) continue;             vector&lt;int&gt; path = findPath(u, minNode, n);             ans[i] = minNode;             // 移除路径上的边(简化处理,实际需更精确标记)             int prev = u;             for (int v : path) {                 auto&amp; vec = adj[prev];                 vec.erase(find(vec.begin(), vec.end(), v));                 auto&amp; vec2 = adj[v];                 vec2.erase(find(vec2.begin(), vec2.end(), prev));                 prev = v;             }         }         for (int i = 1; i &lt;= n; ++i) {             cout &lt;&lt; ans[i] &lt;&lt; (i == n ? "\n" : " ");         }     }     return 0; }</pre><p><br/></p>
解析

方法思路

1、树的表示:使用邻接表表示树的结构。

2、贪心策略:对于每个数字从 1 到 n,找到其当前所在节点所在连通块中编号最小的节点,然后通过路径查找将该数字移动到该最小节点。

3、路径查找:使用广度优先搜索(BFS)查找当前节点到最小节点的路径,并标记路径上的边为已处理,确保后续处理不重复使用这些边。

代码解释

1、输入处理:读取多组测试数据,构建树的邻接表,并记录每个数字的初始节点。

2、查找最小节点:对于每个数字,使用 BFS 查找其所在连通块中编号最小的节点。

3、路径查找:使用 BFS 查找当前节点到最小节点的路径。

4、更新节点与边:将数字移动到最小节点,并移除路径上的边,确保后续处理不重复使用这些边。

5、输出结果:输出每个数字最终所在的节点编号,形成字典序最小的排列。

该方法通过贪心策略和 BFS 路径查找,确保每次将数字移动到最小可能的节点,从而得到字典序最小的结果。