盒子
盒子
文章目录
  1. 前言
  2. 单源最短路
    1. Dijkstra+Heap
    2. SPFA（没有负权边禁用）
  3. 全源最短路
    1. Floyd
  4. 最小生成树
    1. Kruskal
    2. Prim（主要用于稠密图）
  5. 强连通分量
    1. Tarjan
  6. 二分图最大匹配
    1. 匈牙利算法
  7. LCA
    1. 树上倍增
    2. Tarjan

图论模板

2020.07.26 Zhao Yiming  热度 ℃

前言

图论算法千千万，这只蒟蒻团团转。
以下程序大都在洛谷等OJ提交过，保证正确率95%以上（请大佬多多Hack）
程序主要来源：《算法竞赛进阶指南》李煜东著

单源最短路

Dijkstra+Heap

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

const int N=100010,M=1000010;

int head[N],ver[M],edge[M],Next[M],d[N];
bool v[N];
int n,m,s,tot;

priority_queue<pair<int,int> > q;

void add(int x,int y,int z){
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}

void dijkstra(int s){
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));

	d[s]=0;

	q.push(make_pair(0,s));

	while(q.size()){
		int x=q.top().second;
		q.pop();

		if(v[x])
			continue;

		v[x]=1;

		for(int i=head[x];i;i=Next[i]){
			int y=ver[i],z=edge[i];

			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				q.push(make_pair(-d[y],y));
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;

	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}

	dijkstra(s);

	for(int i=1;i<=n;i++)
		printf("%d ",d[i]);

	puts("");
	return 0;
}

SPFA（没有负权边禁用）

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

const int N=100010,M=1000010;

int head[N],ver[M],edge[M],Next[M],d[N];
int n,m,s,tot;
queue<int> q;
bool v[N];

void add(int x,int y,int z){
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}

void spfa(int s){
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));

	d[s]=0;
	v[s]=1;
	q.push(s);

	while(q.size()){
		int x=q.front();
		q.pop();
		v[x]=0;

		for(int i=head[x];i;i=Next[i]){
			int y=ver[i],z=edge[i];

			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				if(!v[y])
					q.push(y),v[y]=1;
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;

	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}

	spfa(s);
	
	for(int i=1;i<=n;i++)
		printf("%d ",d[i]);

	puts("");
	return 0;
}

全源最短路

Floyd

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

int d[310][310],n,m;

int main(){
	cin>>n>>m;

	memset(d,0x3f,sizeof(d));

	for(int i=1;i<=n;i++)
		d[i][i]=0;

	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		d[x][y]=min(d[x][y],z);
	}

	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			printf("%d ",d[i][j]);

		puts("");
	}

	return 0;
}

最小生成树

Kruskal

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

struct rec{
	int x,y,z;
}edge[500010];

int fa[100010],n,m,ans;

bool operator <(rec a,rec b){
	return a.z<b.z;
}

int get(int x){
	if(x==fa[x])
		return x;

	return fa[x]=get(fa[x]);
}

int main(){
	cin>>n>>m;

	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);

	sort(edge+1,edge+m+1);

	for(int i=1;i<=n;i++)
		fa[i]=i;

	for(int i=1;i<=m;i++){
		int x=get(edge[i].x);
		int y=get(edge[i].y);

		if(x==y)
			continue;

		fa[x]=y;
		ans+=edge[i].z;
	}

	cout<<ans<<"\n";
	return 0;
}

Prim（主要用于稠密图）

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

int a[5010][5010],d[5010],n,m,ans;
bool v[5010];

void prim(){
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));

	d[1]=0;

	for(int i=1;i<n;i++){
		int x=0;

		for(int j=1;j<=n;j++)
			if(!v[j] && (x==0 || d[j]<d[x]))
				x=j;

		v[x]=1;
		
		for(int y=1;y<=n;y++)
			if(!v[y])
				d[y]=min(d[y],a[x][y]);
	}
}

int main(){
	cin>>n>>m;

	memset(a,0x3f,sizeof(a));

	for(int i=1;i<=n;i++)
		a[i][i]=0;

	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		a[y][x]=a[x][y]=min(a[x][y],z);
	}

	prim();

	for(int i=2;i<=n;i++)
		ans+=d[i];

	cout<<ans<<"\n";
	return 0;
}

强连通分量

Tarjan

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

const int N=100010,M=1000010;

int ver[M],Next[M],head[N],dfn[N],low[N];
int vc[M],nc[M],hc[N];
int st[N],ins[N],c[N];
vector<int> scc[N];
int n,m,tot,tc,num,top,cnt;

void add(int x,int y){
	ver[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
}

void tarjan(int x){
	dfn[x]=low[x]=++num;
	st[++top]=x,ins[x]=1;

	for(int i=head[x];i;i=Next[i])
		if(!dfn[ver[i]]){
			tarjan(ver[i]);
			low[x]=min(low[x],low[ver[i]]);
		}
		else if(ins[ver[i]])
			low[x]=min(low[x],dfn[ver[i]]);

	if(dfn[x]==low[x]){
		cnt++;
		int y;

		do{
			y=st[top--];
			ins[y]=0;
			c[y]=cnt;
			scc[cnt].push_back(y);
			cout<<y<<" ";
		}while(x!=y);

		puts("");
	}
}

int main(){
	cin>>n>>m;

	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
	}

	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);

	return 0;
}

二分图最大匹配

匈牙利算法

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

int n1,n2,m,ans;
int result[1010];
bool state[1010];
bool dat[1010][1010];

void init(){
	int t1,t2;

	memset(dat,0,sizeof(dat));
	memset(result,0,sizeof(result));
	
	ans=0;
	scanf("%d%d%d",&n1,&n2,&m);

	for(int i=1;i<=m;i++){
		scanf("%d%d",&t1,&t2);
		dat[t1][t2]=true;
	}
}

bool find(int a){
	for(int i=1;i<=n2;i++){
		if(dat[a][i]==1&&!state[i]){
			state[i]=true;

			if(result[i]==0||find(result[i])){
				result[i]=a;
				return true;
			}
		}
	}

	return false;
}

int main(){
	init();

	for(int i=1;i<=n1;i++){
		memset(state,0,sizeof(state));

		if(find(i))
			ans++;
	}

	printf("%d\n",ans);

	return 0;
}

LCA

树上倍增

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
#include <bits/stdc++.h>
using namespace std;

const int SIZE=500010;

int f[SIZE][20],d[SIZE],dist[SIZE];
int ver[2*SIZE],Next[2*SIZE],edge[2*SIZE],head[SIZE];
int T,n,m,tot,t;
queue<int> q;

void add(int x,int y,int z){
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}

void bfs(){
    q.push(1);
    d[1]=1;
    
    while(q.size()){
        int x=q.front();
        q.pop();
        
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            
            if(d[y])
                continue;
                
            d[y]=d[x]+1;
            dist[y]=dist[x]+edge[i];
            f[y][0]=x;
            
            for(int j=1;j<=t;j++)
                f[y][j]=f[f[y][j-1]][j-1];
                
            q.push(y);
        }
    }
}

int lca(int x,int y){
    if(d[x]>d[y])
        swap(x,y);
        
    for(int i=t;i>=0;i--)
        if(d[f[y][i]]>=d[x])
            y=f[y][i];
            
    if(x==y)
        return x;
        
    for(int i=t;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
            
    return f[x][0];
}

int main(){
    cin>>T;
    
    while(T--){
        cin>>n>>m;
        
        t=(int)(log(n)/log(2))+1;
        
        for(int i=1;i<=n;i++)
            head[i]=d[i]=0;
            
        tot=0;
        
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        
        bfs();
        
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]);
        }
    }
    
    return 0;
}

Tarjan

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
#include <bits/stdc++.h>
using namespace std;

const int SIZE=500010;
int ver[2*SIZE],Next[2*SIZE],edge[2*SIZE],head[SIZE];
int fa[SIZE],d[SIZE],v[SIZE],lca[SIZE],ans[SIZE];
vector<int> query[SIZE],query_id[SIZE];
int T,n,m,tot,t;

void add(int x,int y,int z){
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}

void add_query(int x,int y,int id){
    query[x].push_back(y);
    query_id[x].push_back(id);
    query[y].push_back(x);
    query_id[y].push_back(id);
}

int get(int x){
    if(x==fa[x])
        return x;
        
    return fa[x]=get(fa[x]);
}

void tarjan(int x){
    v[x]=1;
    
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        
        if(v[y])
            continue;
            
        d[y]=d[x]+edge[i];
        
        tarjan(y);
        
        fa[y]=x;
    }
    
    for(int i=0;i<query[x].size();i++){
        int y=query[x][i],id=query_id[x][i];
        
        if(v[y]==2){
            int lca=get(y);
            ans[id]=min(ans[id],d[x]+d[y]-2*d[lca]);
        }
    }
    
    v[x]=2;
}

int main(){
    cin>>T;
    
    while(T--){
        cin>>n>>m;
        
        for(int i=1;i<=n;i++){
            head[i]=0;
            fa[i]=i;
            v[i]=0;
            
            query[i].clear();
            query_id[i].clear();
        }
        
        tot=0;
        
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            
            if(x==y)
                ans[i]=0;
            else{
                add_query(x,y,i);
                ans[i]=1<<30;
            }
        }
        
        tarjan(1);
        
        for(int i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    
    return 0;
}

持续更新中……

本文作者：Zhao Yiming Zhao Yiming

本文链接： https://zhaoyiming313.github.io/2020/07/26/图论模板/

版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 4.0 国际许可协议，转载请注明。