题目链接:HDU 4607 Park Visit
给定一个无根树,边权为1,选取树中的k个结点,构成子树。使得遍历子树的路径和最短。
思路:希望遍历的时候尽可能少的分叉。因为分叉后访问节点需要返回,路径翻倍。因此考虑求原无向图的最长路径,然后k个节点剩下的节点再用分叉的节点来补充。
假设最长链长度为m,则当k<=m时,需要通过的路径为k-1。当k>m时,需要通过的路径长为(k-m)*2 + m - 1。
无向图的最长链可以用O(n)实现。做法是使用BFS或者DFS找到所有分支中最长的分支的端点。然后在从这一端点BFS或者DFS找到另外一边端点,两个端点之间的距离就是无向图的最长链长度。
//#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5+5;
vector<int> G[maxn];
bool vis[maxn];
// bfs version
pair<int, int> bfs(int s) {
queue<pair<int, int> > que;
pair<int, int> p_cur;
int cur;
vis[s] = true;
que.push(make_pair(s, 1));
while(!que.empty()) {
p_cur = que.front();
cur = p_cur.first;
que.pop();
for(int i = 0; i < G[cur].size(); ++i) {
if(!vis[G[cur][i]]) {
vis[G[cur][i]] = true;
que.push(make_pair(G[cur][i], p_cur.second+1));
}
}
}
return p_cur;
}
int MaxTreeDistance(int n) {
pair<int, int> ans = bfs(1);
fill(vis+1, vis+1+n, false);
ans = bfs(ans.first);
return ans.second;
}
//dfs version
void dfs(int v, int dis, int& ans_v, int& ans_dis) {
if(ans_dis < dis) {
ans_dis = dis;
ans_v = v;
}
vis[v] = true;
for(int i = 0; i < G[v].size(); ++i) {
if(!vis[G[v][i]]) {
dfs(G[v][i], dis+1, ans_v, ans_dis);
}
}
}
int MaxTreeDistance_DFS(int n) {
int ans_v = -1, ans_dis = 0;
dfs(1, 1, ans_v, ans_dis);
fill(vis+1, vis+1+n, false);
dfs(ans_v, 1, ans_v, ans_dis);
return ans_dis;
}
int main()
{
cin.tie(0);
cin.sync_with_stdio(false);
int n, m, t, q; // 节点数(1-n)和边数
int tree_dis = 0;
int x, y;
cin >> t;
while(t--) {
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
for(int i = 0; i < n-1; ++i) {
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
fill(vis+1, vis+n+1, false);
// tree_dis = MaxTreeDistance(n);
tree_dis = MaxTreeDistance_DFS(n);
//cout << tree_dis << endl;
while(m--){
cin >> q; // q <=n
if(q <= tree_dis) cout << q - 1 << endl;
else cout << 2 * (q-tree_dis) + tree_dis - 1 << endl;
}
}
//system("pause");
return 0;
}
本文由 shinelin 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Apr 7, 2019 at 09:23 am