最小树形图（朱刘算法）
树形图：有向图中无环，每个点的入度为1（根节点除外）的图
最小树形图：边权和最小的树形图，可以认为是有向图的最小生成树
朱刘算法
步骤：
- 对于每个点（除了根节点），找出所有入边中权值最小的边
- 判断选出的边中是否存在环。若不存在环，则这些边构成最小树形图，答案加上选出的边的权值，算法结束；若存在环，则进行下一步。
- 将所有的环缩点，得到新图$G$。
- 删去环内部的边，把终点在环内部的边的权值减去其终点在环内部的入边的权值，其他边不变。
- 进行步骤2。
时间复杂度$O(nm)$
模板题
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| #include<bits/stdc++.h>
using namespace std;
const int N=105;
const int INF=0x3f3f3f3f;
int n,m,r;
int d[N][N],bd[N][N];
int pre[N],bpre[N];
int dfn[N],low[N],timestamp;
stack<int>s;
bool st[N],ins[N];
int id[N],cnt;
void dfs(int u){
st[u]=true;
for(int i=1;i<=n;i++){
if(d[u][i]!=INF&&!st[i])dfs(i);
}
}
bool check_con(){
memset(st,0,sizeof st);
dfs(r);
for(int i=1;i<=n;i++){
if(!st[i])return false;
}
return true;
}
void tarjan(int u){
dfn[u]=low[u]=++timestamp;
s.push(u),ins[u]=true;
int j=pre[u];
if(!dfn[j]){
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(ins[j]){
low[u]=min(low[u],dfn[j]);
}
if(low[u]==dfn[u]){
int y;
++cnt;
do{
y=s.top();
s.pop();
ins[y]=false;
id[y]=cnt;
}while(y!=u);
}
}
int work(){
int res=0;
while(true){
for(int i=1;i<=n;i++){
pre[i]=i;
for(int j=1;j<=n;j++){
if(d[pre[i]][i]>d[j][i]){
pre[i]=j;
}
}
}
memset(dfn,0,sizeof dfn);
timestamp=cnt=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
if(cnt==n){
for(int i=1;i<=n;i++){
if(i!=r){
res+=d[pre[i]][i];
}
}
break;
}
for(int i=1;i<=n;i++){
if(i!=r){
if(id[pre[i]]==id[i]){
res+=d[pre[i]][i];
}
}
}
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
bd[i][j]=INF;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(d[i][j]<INF&&id[i]!=id[j]){
int a=id[i],b=id[j];
if(id[pre[j]]==id[j])bd[a][b]=min(bd[a][b],d[i][j]-d[pre[j]][j]);
else bd[a][b]=min(bd[a][b],d[i][j]);
}
}
}
n=cnt;
r=id[r];
memcpy(d,bd,sizeof d);
}
return res;
}
int main(){
memset(d,0x3f,sizeof d);
cin >> n >> m >> r;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
if(a!=b&&b!=r)d[a][b]=min(d[a][b],c);
}
if(!check_con())cout << "-1\n";
else cout << work() << endl;
return 0;
}
|