圆方树学习笔记 | Bill Yang's Blog

圆方树学习笔记

补坑防忘。

学习笔记

见多年前制作的ppt

模板

注意!!!以下代码均未处理二元环!!!

不带权仙人掌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
vector<int>edges[maxn],tree[maxn];
int n,m,step=0,Lowlink[maxn],Dfn[maxn],BCC=0,New,Square[maxn],Belong[maxn];
struct St {
int u,v;
};
stack<St>S;
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void AddEdge2(int x,int y) {
tree[x].push_back(y);
}
void Tarjan(int Now,int fa) { //构建圆方树
step++;
Lowlink[Now]=Dfn[Now]=step;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(!Dfn[Next]) {
S.push((St) {
Now,Next
});
Tarjan(Next,Now);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
if(Dfn[Now]<Lowlink[Next])AddEdge2(Now,Next),S.pop();
else if(Dfn[Now]==Lowlink[Next]) { //构成点双连通分量
BCC++;
AddEdge2(Now,++New);
Square[New]=1;
while(!S.empty()) {
int u=S.top().u;
S.pop();
if(u==Now)break;
Belong[u]=BCC;
AddEdge2(New,u);
}
}
} else if(Next!=fa&&Lowlink[Now]>Dfn[Next]) {
Lowlink[Now]=Dfn[Next];
S.push((St) {
Now,Next
});
}
}
}

带权仙人掌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct Edge {
int from,to,dist;
};
vector<Edge>edges[maxn],edges2[maxn];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {
x,y,v
});
}
void AddEdge2(int x,int y,int v) {
edges2[x].push_back((Edge) {
x,y,v
});
}
int step=0,Lowlink[maxn],Dfn[maxn],BCC=0,Length[maxn],f[maxn],Belong[maxn],vst[maxn],Square[maxn];
struct St {
int u,v,dist;
};
stack<St>S;
vector<int>Circle[maxn];
void Tarjan(int Now,int fa) {
step++;
Lowlink[Now]=Dfn[Now]=step;
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(!Dfn[Next]) {
S.push((St) {
Now,Next,e.dist
});
Tarjan(Next,Now);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
if(Dfn[Now]<Lowlink[Next])AddEdge2(Now,Next,e.dist),S.pop();
else if(Dfn[Now]==Lowlink[Next]) { //构成点双连通分量
BCC++;
AddEdge2(Now,++New,0);
Square[New]=1;
while(!S.empty()) {
int u=S.top().u,v=S.top().v,dist=S.top().dist;
S.pop();
Length[BCC]+=dist;
f[u]=f[v]+dist;
if(u!=Now) {
Belong[u]=BCC;
Circle[New].push_back(u);
}
if(u==Now&&v==Next)break;
}
for(int i=0; i<Circle[New].size(); i++) {
int Next=Circle[New][i];
AddEdge2(New,Next,min(abs(f[Next]-f[Now]),Length[BCC]-abs(f[Next]-f[Now])));
}
}
} else if(Next!=fa&&Lowlink[Now]>Dfn[Next]) {
Lowlink[Now]=Dfn[Next];
S.push((St) {
Now,Next,e.dist
});
}
}
}
姥爷们赏瓶冰阔落吧~
0%