 /**//*
一棵有向樹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
搜索
最新評論

|
|