朱刘算法

发表于 更新于 分类于 阅读次数： Changyan：

朱刘算法

有向图的类Prim算法，找有向图的最小生成树。

最小树形图

树形图：

  • 无有向环
  • 除了根节点外，每个点入度为1

以某个点为根的一棵有向树，其边权之和为图中所有树形图中是最小的称为最小树形图。

朱刘算法 $O(nm)$

(1) 除了根节点外对每个点选取一条边权最小的入边

(2)判断当前(选出的边)组成的图中有无环

​ 1.若无环：则说明当前图已经为构造好的最小生成树，算法结束

​ 2.若有环：进行第(3)步

(3)将构造的图进行强连通分量缩点，得到新图$G’$,对于$G’$中的所有边

​ 1.如果是环中的边：直接删去

​ 2.如果终点在环内(即新缩的点)：更新此边权权值为$W-W_{环内}$

​ 3.其他边：不变

然后继续从(1)开始迭代

当迭代完成后,所有选择的边的边权之和就是最终的答案。

邻接矩阵版本：

由于复杂度是 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
const int N = 110,M=2e4+10,INF=1e8;
int n,m,r;
int d[N][N],bd[N][N],g[N][N];
int pre[N],bpre[N];
int dfn[N],low[N],timestamp,stk[N],top;
int id[N],scc_cnt;
bool st[N],ins[N];

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);
	rep(i,1,n) 
		if(!st[i]) 
			return false;
	return true;
}

void tarjan(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=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;
		scc_cnt ++;
		do{
			y=stk[top --];
			ins[y]=false;
			id[y]=scc_cnt;
		}while(y!=u);
	}
}

int zhuliu(){
	int ans = 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=scc_cnt=0;
		for(int i=1;i<=n;++i) 
			if(!dfn[i])
				tarjan(i);
		
		
		if(scc_cnt == n){
			for(int i=1;i<=n;++i) {
				if(i==r) continue;
				ans += d[pre[i]][i];
			}
			break ;
		}
		
		for(int i=1;i<=n;++i){
			if(i==r) continue;
			if(id[pre[i]] == id[i]){ 
				ans += d[pre[i]][i];
			}
		}
		
		for(int i=1;i<=scc_cnt;++i)
			for(int j=1;j<=scc_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]);
				}
			}
		}
		r=id[r];
		n = scc_cnt;
		memcpy(d,bd,sizeof d);	
	}
	return ans;
}

void solve(){
	n=read(),m=read(),r=read();
	rep(i,1,m) {
		int u=read(),v=read(),w=read();
		d[u][v]=min(d[u][v],w);
	}
	// rep(i,1,n) rep(j,1,n) debug(d[i][j]);
	if(!check_con()) puts("-1");
	else print(zhuliu());
}

模板题

在一个二维平面中求 一个最小树形图

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
const int N = 110, M = 10010, INF=1e8;
int n,m,k;
pdd q[N];
bool g[N][N];
double d[N][N],bd[N][N]; //d数组用来存距离，bd数组用来存储备份
int pre[N],bkppre[N];  //pre数组用来存储备份，bkppre数组用来存储前去的备份
int dfn[N],low[N],timestamp,stk[N],top;
int id[N],scc_cnt=0;
bool st[N],ins[N];

void dfs(int u){
    st[u]=true;
    rep(i,1,n) if(g[u][i]&&!st[i]) dfs(i);
}

bool check_con(){
    memset(st,0,sizeof st);
    dfs(1);
    rep(i,1,n) if(!st[i]) return false;
    return true;
}

double get_dist(int a,int b){
    double dx = q[a].x-q[b].x;
    double dy = q[a].y-q[b].y;
    return sqrt(dx*dx+dy*dy);
}

void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=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;
        scc_cnt ++;
        do{
            y=stk[top --];
            ins[y]=false;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}

double zhuliu(){
    double ans= 0;
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n;++j)
            if(g[i][j]) d[i][j] = get_dist(i,j);
            else d[i][j] = INF;
    
    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;
            }
        }
        
        //tarjan找环
        memset(dfn,0,sizeof dfn);
        timestamp=scc_cnt=0;
        for(int i=1;i<=n;++i) 
            if(!dfn[i]) 
                tarjan(i);
            
        //缩点后无环,累加答案后算法结束
        if(scc_cnt == n) {
            for(int i=2;i<=n;++i) ans += d[pre[i]][i];
            break;
        }
        
        //累加所有环内的边
        for(int i=2;i<=n;++i)
            if(id[pre[i]]==id[i])
                ans += d[pre[i]][i];
                
        //清空bd数组,准备存储缩点完更新的边权 
        for(int i=1;i<=scc_cnt;++i)
            for(int j=1;j<=scc_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 = scc_cnt;
        memcpy(d,bd,sizeof d);
    }
    
    return ans;
}

void solve(){
    rep(i,1,n) scanf("%lf%lf",&q[i].x,&q[i].y);
    
    memset(g,0,sizeof g);
    while(m--){
        int a=read(),b=read();
        if(a!=b&&b!=1) g[a][b]=true;
    }
    if(!check_con()) puts("poor snoopy");
    else printf("%.2lf\n",zhuliu());
}
//=================================
int main(){
	while(~scanf("%d%d",&n,&m)){
	    solve();
	}
	return 0;
}