Codeforces 965E Short Code Trie树+贪心（启发式合并）
Trie 贪心 启发式合并   发布于 2019-08-03   322人围观  0条评论
Trie 贪心 启发式合并   发表于 2019-08-03   322人围观  0条评论

## 代码

```#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
string s[maxn];
int cnt = 0;
struct tree_node{
int ch[26];
int dep;
int en;
}tr[maxn<<4];
int dep[maxn];
typedef pair<int,int>PI;
priority_queue<PI>q[maxn];
int ans = 0;
void build(int x,int now,int depth){
int len = s[x].size();
for(int i = 0;i < len;++i){
char t = s[x][i];
if(tr[now].ch[t - 'a'] == -1){
tr[now].ch[t-'a'] = ++cnt;
tr[cnt].dep = tr[now].dep + 1;
for(int i = 0;i < 26;++i)
tr[cnt].ch[i] = -1;
tr[cnt].en = 0;
}
now = tr[now].ch[t-'a'];
}
tr[now].en = 1;
return;
}
void check(int now){
if(now == -1)return;
while(!q[now].empty())q[now].pop();
for(int i = 0;i < 26;++i){
int v = tr[now].ch[i];
check(v);
while(!q[v].empty()){
q[now].push(q[v].top());
q[v].pop();
}
}
if(now != 0 && !q[now].empty() && !tr[now].en){
tr[now].en++;
tr[q[now].top().second].en--;
q[now].pop();
}
if(tr[now].en == 1){
q[now].push(make_pair(tr[now].dep,now));
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(tr,-1,sizeof(tr));
cin >> n;
for(int i = 1;i <= n;++i){
cin >> s[i];
}
tr[0].dep = 0;
tr[0].en = 0;
for(int i = 1;i <= n;++i){
build(i,0,0);
}
check(0);
while(!q[0].empty()){
ans += tr[q[0].top().second].dep;
q[0].pop();
}
cout << ans << endl;
}```

0 条评论