首页 > 代码库 > *[codility]Country network
*[codility]Country network
https://codility.com/programmers/challenges/fluorum2014
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1273
http://blog.csdn.net/caopengcs/article/details/36872627
http://www.quora.com/How-do-I-determine-the-order-of-visiting-all-leaves-of-a-rooted-tree-so-that-in-each-step-I-visit-a-leaf-whose-path-from-root-contains-the-most-unvisited-nodes#
思路如曹博所说，先dfs记录离根的距离，来的方向的前驱。然后按距离排序，之后按此排序求有意义的增加距离。
直观感受是，如果两个叶子在一个分叉上，显然深的节点更先被访问，如果不在一个分叉上，那么先算深的也没什么损失。最后，按照这个权值再对叶子排序一次，就是所要的结果。
#include <iostream>using namespace std;void dfs(vector<vector<int>> &tree, vector<int> &parent, vector<int> &depth, vector<bool> &visited, int root, int dep) { visited[root] = true; depth[root] = dep; for (int i = 0; i < tree[root].size(); i++) { if (visited[tree[root][i]]) continue; parent[tree[root][i]] = root; dfs(tree, parent, depth, visited, tree[root][i], dep + 1); }}vector<int> solution(int K, vector<int> &T) { int n = T.size(); vector<vector<int>> tree(n); for (int i = 0; i < n; i++) { if (T[i] != i) { tree[i].push_back(T[i]); tree[T[i]].push_back(i); } } vector<int> parent(n); vector<int> depth(n); vector<bool> visited(n); dfs(tree, parent, depth, visited, K, 0); vector<vector<int>> cnt(n); for (int i = 0; i < n; i++) { cnt[depth[i]].push_back(i); } vector<int> ordered; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < cnt[i].size(); j++) { ordered.push_back(cnt[i][j]); } } vector<int> res; vector<int> length(n); visited.clear(); visited.resize(n); visited[K] = true; for (int i = 0; i < ordered.size(); i++) { int len = 0; int x = ordered[i]; while (!visited[x]) { visited[x] = true; x = parent[x]; len++; } length[ordered[i]] = len; //cout << "length[" << ordered[i] << "]:" << len << endl; } cnt.clear(); cnt.resize(n); for (int i = 0; i < length.size(); i++) { cnt[length[i]].push_back(i); } res.push_back(K); for (int i = cnt.size() - 1; i > 0; i--) { for (int j = 0; j < cnt[i].size(); j++) { res.push_back(cnt[i][j]); } } return res;}
*[codility]Country network
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。