算法笔记--圆方树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记--圆方树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2316字,纯文字阅读大概需要4分钟。
内容图文
![算法笔记--圆方树](/upload/InfoBanner/zyjiaocheng/1133/7676ec48fee44878b97f98f3e2746eca.jpg)
模板:
struct Circle_Square_Tree {
const static int N = 2e4 + 10;
vector<pair<int, LL> > G[N];
int dp[N], anc[N][18], n;
LL dis[N], cir[N]; //环的大小
bool vis[N];//记录到方点的最短距离是否经过回边
vector<pii> g[N];
int dfn[N], low[N], fa[N], cnt, tot;
int a[N];
inline void solve(int u, int v, int d) {
int cnt = 0;
LL sum = d;
for (int i = v; i != u; i = fa[i]) sum += dis[i] - dis[fa[i]], a[++cnt] = i;
a[++cnt] = u;
LL DIS = 0;
++tot;
for (int i = cnt; i >= 1; --i) {
LL D = min(DIS, sum-DIS);
if(D == DIS) vis[a[i]] = true;
else vis[a[i]] = false;
G[a[i]].pb({tot, D});
G[tot].pb({a[i], D});
DIS += dis[a[i-1]]-dis[a[i]];
}
cir[tot] = sum;
}
inline void tarjan(int u, int o) {
fa[u] = o;
dfn[u] = low[u] = ++cnt;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v == o) continue;
if(!dfn[v]) {
dis[v] = dis[u] + w;
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], dfn[v]);
if(low[v] > dfn[u]) {
G[u].pb({v, w});
G[v].pb({u, w});
}
}
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
if(v == o) continue;
if(fa[v] != u && dfn[v] > dfn[u]) {
solve(u, v, w);
}
}
}
inline void dfs(int u, int o) {
anc[u][0] = o;
dp[u] = dp[o] + 1;
for (int i = 1; i < 18; ++i) anc[u][i] = anc[anc[u][i-1]][i-1];
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].fi;
LL w = G[u][i].se;
if(v == o) continue;
dis[v] = dis[u] + w;
dfs(v, u);
}
}
inline void init(int _n) {
tot = n = _n;
cnt = 0;
dis[0] = dp[1] = 0;
tarjan(1, 0);
dfs(1, 1);
}
inline int lca(int u, int v) {
if(dp[u] < dp[v]) swap(u, v);
for (int i = 17; i >= 0; --i) if(dp[anc[u][i]] >= dp[v]) u = anc[u][i];
if(u == v) return u;
for (int i = 17; i >= 0; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][0];
}
inline int jump(int u, int lca) {
for (int i = 17; i >= 0; --i) if(dp[anc[u][i]] > dp[lca]) u = anc[u][i];
return u;
}
inline LL query(int u, int v) {
int l = lca(u, v);
if(l <= n) return dis[u]+dis[v]-2*dis[l];
int uu = jump(u, l), vv = jump(v, l);
LL d1 = dis[uu]-dis[l], d2 = dis[vv]-dis[l];
if(!vis[uu]) d1 = cir[l]-d1;
if(!vis[vv]) d2 = cir[l]-d2;
return dis[u]-dis[uu]+dis[v]-dis[vv]+min(abs(d1-d2), cir[l]-abs(d1-d2));
}
}CST;
原文:https://www.cnblogs.com/widsom/p/11468827.html
内容总结
以上是互联网集市为您收集整理的算法笔记--圆方树全部内容,希望文章能够帮你解决算法笔记--圆方树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。