HDU 4607 Park Visit (树的最长链)

in 刷题 with 0 comment

题目链接：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

← → ↓ ↑
Comments are closed.