寻找牛妹

[编程题]寻找牛妹

热度指数：459 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n个房间，房间之间有通道相连，一共有n-1个通道，每两个房间之间都可以通过通道互相到达。

牛牛一开始在1号房间。牛妹在某个另外的房间。牛牛想去寻找牛妹，但是他没有地图，所以只能在房间之间乱走。

牛牛每走过一条通道需要花费1金币，每条通道最多只能走两次。

牛牛有一个乱走规则：如果当前牛牛有 没走过的通道 可以走，牛牛就不会去走 走过一次的通道

这个规则可以保证只要钱足够就一定可以找到牛妹。

有m个查询，每次询问如果牛妹在 $x_i$ 号房间，请问牛牛身上至少要带多少金币才可以保证任何情况下都可以找到牛妹。

示例1

输入

4,1,[1,2,2],[2,3,4],[3]

输出

[4]

说明

花费金币最多的方案是1->2->4->2->3

备注:



第一个参数n代表房间数量
第二个参数m代表查询数量
第三、四个参数vector u,v代表通道，与通过通道相连
第五个参数vector x代表m次查询中牛妹的位置

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 寻找牛妹
     * @param n int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return int整型vector
     */
    vector<int> G[200003];
    int d[200003], f[200003];
    int DFS(int u, int p, int k){
        int cnt = 0;
        for(auto &x: G[u]){
            if(x == p)
                continue;
            cnt += DFS(x, u, k+1);
        }
        f[u] = cnt;
        d[u] = k;
        return cnt+1;
    }
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        vector<int> r;
        memset(d, 0, sizeof(d));
        memset(f, 0, sizeof(f));
        for(int i=0;i<n-1;i++){
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        DFS(1, -1, 0);
        for(auto &t: x)
            r.push_back(d[t] + 2*(n-1-d[t]-f[t]));
        return r;
    }
};

发表于 2020-07-22 18:08:29 回复(0)

繁星似尘

最糟糕的情况，就是把能走两次的通道都走两次，那么，哪些通道能走两次？给的图可以看做是一个以1号结点为根的树，显然，目标结点的子结点是不能经过的，从根到目标结点的通道只能通过一次，其他结点均可以通过两次。因此，本题只要统计目标结点到根的的距离和子结点的个数就可以解决。代码如下。

int dfs(vector<vector<int>> &graph,vector<int> &subNodes,vector<int> &height,int k,int cur,int pre){
    int count = 0;
    for(int i=0;i<graph[cur].size();i++){
        if(graph[cur][i] == pre){
            continue;
        }
        count += dfs(graph,subNodes,height,k+1,graph[cur][i],cur);
    }
    subNodes[cur] = count; 
    height[cur] = k;
    return count+1;
}

vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
    vector<vector<int>> graph(n+1);
    for(int i=0;i<u.size();i++){
        graph[u[i]].push_back(v[i]);
        graph[v[i]].push_back(u[i]);
    }    
    vector<int> subNodes(n+1,0);
    vector<int> height(n+1,0);
    dfs(graph,subNodes,height,0,1,-1);
    vector<int> res;
    for(int i=0;i<m;i++){
        int count = 1 * height[x[i]] + 2 * (n - 1 - height[x[i]] - subNodes[x[i]]);
        res.push_back(count);
    }
    return res;
}

编辑于 2020-07-05 11:37:52 回复(0)