/**//* 一棵有向树n<=1000 "directed roads" 0是根,现要对其所有边编号,每个点出去的边的编号不能相同 这样,0到叶子i就有一条编好号的路径了pathi,要求最小化这些叶子的路径集合{pathi} 两个路径集合{pathi},{pathi'}的比较是,先各自元素排序(即字典序) 然后比较这两个集合,也是字典序 然后q个询问,问排第c小的路径
解题报告说即是标号得到Trie树了~~~~
我就以下贪心了: ①对一个节点u的儿子节点v排序的依据是,谁的子树的叶子深度最小的那个优先 相同的话,谁的子树规模大的优先,这样过不了下面的数据: 0-1 0-2 1-3 1-4 4-5 2-6 其实这个贪心的处理太模糊了,仅仅依靠深度最小的叶子不够的 而且比较子树规模也不行,子树规模相同,但树的形状可以很不同!!
②在以上的基础上,再具体一下,就是为每个节点u存下它的所有叶子的深度(当然要排序) 排序比较时: 逐个元素比较,若a的某个叶子深度与b的不同,return leaf[a][i] < leaf[b][i] 都相同时,说明某个是某个的前缀了,选择叶子多的 这样有问题的,没处理“所有叶子深度都相同而且叶子数一样的”情况 比如下面数据: 0-1 0-2 1-3 3-4 3-5 2-6 2-7 6-8 7-9
③再进一步具体,保存每个节点u其到所有叶子的路径vector<vector<int>> leaf[u] 然后比较时,跟②类似。 先逐个比较,若leaf[a][i] != leaf[b][i] return leaf[a][i] < leaf[b][i] 否则,说明它们的前缀相同,return leaf[a].size() > leaf[b].size() (返回规模大的,因为需要 为其前面加上小字符,必然数量越多越好) ”只看叶子深度最小,相同的就看规模大的“ => ”看所有叶子的深度“ => ”看所有叶子的路径“
注意clear,否则会爆内存 我上面的做法比较慢,因为保存了所有路径 watashi的很快~~
读题要仔细呀,我是看了watashi的翻译在原文找出单词的,明白题意~~~ */ #include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cmath> #include<string> #include<cstdlib> #include<vector> #include<cstdio> #include<set> #include<list> #include<numeric> #include<cassert> #include<ctime> #include<bitset>
using namespace std;
const int INF = 1000000000; const int MAXN = 1010;
vector<int> E[MAXN]; vector<vector<int> > leaf[MAXN];
bool cmp(int a, int b){ int len = min(leaf[a].size(), leaf[b].size()); for(int i = 0; i < len ; i ++) { if(leaf[a][i] != leaf[b][i]){ return leaf[a][i] < leaf[b][i]; } } return leaf[a].size() > leaf[b].size(); }
void dfs(int u){ leaf[u].clear(); if(E[u].empty()){ leaf[u].push_back(vector<int>()); return; } for(vector<int>::iterator it = E[u].begin(); it != E[u].end() ; it++) { dfs(*it); }
sort(E[u].begin(), E[u].end(), cmp);
int label = 0; for(vector<int>::iterator it = E[u].begin(); it != E[u].end() ; it++, label ++) { for(vector<vector<int> >::iterator jt = leaf[*it].begin(); jt != leaf[*it].end();jt++){ jt->insert(jt->begin(), label); leaf[u].push_back(*jt); } leaf[*it].clear(); } //sort(leaf[u].begin(),leaf[u].end());//由于E[]sort过,这里不用sort了 }
int main() { #ifndef ONLINE_JUDGE //freopen("in","r",stdin); freopen("out","w",stdout); #endif
int line = 0; int T, n, q; int u,v; for (scanf("%d", &T); T--; ) { scanf("%d%d", &n,&q); for (int i = 0 ; i < n ; i ++) { E[i].clear(); } for (int i = 1; i < n; i ++) { scanf("%d%d", &u, &v); E[u].push_back(v); }
dfs(0); vector<vector<int> > &ans = leaf[0]; while(q--){ scanf("%d", &u); u--; if(u >= ans.size()) { puts("Out of range."); }else { for(int i = 0; i < ans[u].size() ; i++) { if(i > 0){ printf(" "); } printf("%d", ans[u][i]); } puts(""); } } puts(""); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|