 /**//*
一棵有向树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
搜索
最新评论

|
|