图论基础

图论基础算法

DFS n个数字 有多少排列顺序

DFS，即深搜，对一棵树，选择不走到结束，不回头的算法，使用递归实现.

给定一个整数 n，将数字1 ~ n排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。

范围
$$
1 <= n <= 7
$$

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
#include<iostream>

using namespace std;

int n, cot[15];
bool st[15];

void dfs(int u)
{
	if(u == n)
	{
		for(int i = 0;i < n;i ++) cout << cot[i] << ' ';
		cout << endl;
		return ;
	}
	for(int i = 1;i <= n;i ++)
	{
		if(!st[i])
		{
			cot[u] = i;
			st[u] = true;
			dfs(u + 1);
			st[u] = false; 
		}
	}
}
void solve()
{
	cin >> n;
	dfs(0);
}
int main()
{
    solve();

	return 0;
}

进阶版

游游想知道，有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。你能帮帮她吗？我们定义，长度为n的排列值一个长度为n的数组，其中1到n每个元素恰好出现了一次。（来源：牛客网）范围
$$
2 <= n <= 10
$$

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
#include<iostream>

using namespace std;

int n, ans, cot[15];
bool st[15], f	[25];

void dfs(int u)
{

	if(u >= 2 && f[cot[u - 1] + cot[u - 2]]) return ;

	if(u == n)
	{
		ans ++;
		return ;
	}

	for(int i = 1;i <= n;i ++)
	{
		if(!st[i])
		{
			cot[u] = i;
			st[i] = true;
			dfs(u + 1);
			st[i] = false; 
		}
	}
}

void solve()
{
	cin >> n;
	f[3] = true, f[5] = true, f[7] = true;
	f[11] = true, f[13] = true, f[17] = true;
	f[19] = true;

	dfs(0);

	cout << ans << endl;
}

int main()
{
    solve();

	return 0;
}

BFS 走出迷宫

BFS，一层一层的搜索，使用queue实现

给定一个迷宫，有入口，需要让找到一条从入口到出口的最短路线。

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
#include<iostream>
#include<queue>

using namespace std;

const int N = 1e5 + 10;
typedef pair<int,int> pII;

int f[110][110];
int dx[4] = {0,0,1,-1}, dy[4]= {1,-1,0,0};
int book[110][110];
queue<pII> q;
int n, m;

void move(int x,int y)
{
	for(int i = 0;i < 4;i ++)
	{
		int mx = dx[i] + x, my = dy[i] + y;

		if(f[mx][my] && !book[mx][my] && mx > 0 && mx <= n && my > 0 && my <= m)
		{
			q.push(pII(mx,my));
			book[mx][my] = 1;
			f[mx][my] += f[x][y];
		} 
	}
}

void solve()
{

	cin >> n >> m;
	for(int i = 1;i <= n;i ++)
		for(int j = 1; j <= m;j ++)
		{
			cin >> f[i][j];
			f[i][j] = !f[i][j];
		}

	q.push(pII(1,1));
	book[1][1] = 1;

	while(q.size())
	{
		auto t = q.front();q.pop();

		move(t.first,t.second);
	}

	cout << f[n][m] - 1 << endl;
}

int main()
{
    solve();

	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
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int n, m, ans = N,st[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
	st[u] = 1;

	int size = 0, sum = 0;

	for(int i = h[u];i != -1;i = ne[i])
	{
		int j = e[i];
		
		if(st[j]) continue;

		int s = dfs(j);
		size = max(size,s);
		sum += s;
	}
	size = max(size,n - sum - 1);

	ans = min(ans,size);

	return sum + 1;
}

void solve()
{
	memset(h,-1,sizeof h);

	cin >> n;
	
	for(int i = 0;i < n - 1;i ++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}

	dfs(1);

	cout << ans << endl;
}

int main()
{
    solve();

	return 0;
}

图的层次遍历

给定一个图，找到从1到n的最短距离，如果找不到输出-1

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
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;
const int N = 1e5 + 10;
int h[N], ne[N], e[N], idx;
int di[N];

void add(int a,int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void solve()
{
	int n, m;
	memset(h,-1,sizeof h);
	memset(di,-1,sizeof di);

	cin >> n >> m;
	while(m --)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	queue<int> q;
	q.push(1);

	di[1] = 0;

	while(q.size())
	{
		int t = q.front();q.pop();

		for(int i = h[t];i != -1;i = ne[i])
		{
			int j = e[i];

			if(di[j] == -1)
			{
				di[j] = di[t] + 1;
				q.push(j);
			}
		}
	}
	cout << di[n] << endl;
}

int main()
{
    solve();

	return 0;
}

拓扑排序

给一个有向图，输出任意一个拓扑排序，如果没有输出 -1。

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
#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int cot[N], q[N], n, m;

void add(int a,int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void solve()
{
	memset(h,-1,sizeof h);
	
	cin >> n >> m;
	while(m --)
	{
		int a, b;
		cin >> a >> b;
		cot[b] ++;
		add(a, b);
	}
	
	int tt = -1, hh = 0;

	for(int i = 1; i <= n;i ++)
		if(!cot[i]) q[++ tt] = i;
    
	while(hh <= tt)
	{
		int t = q[hh ++];
		
		for(int i = h[t];i != -1;i = ne[i])
		{
			int j = e[i];
			if(-- cot[j] == 0)
				q[++ tt] = j;
		}
	}

	if(tt == n - 1) for(int i = 0;i < n;i ++) cout << q[i] << ' ';
	else cout << -1 << endl;
}

int main()
{
    solve();

	return 0;
}

Dijkstra求最短路

这里直接给出堆优化版本

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
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
const int N = 2e5 + 10;
typedef pair<int,int> pII;

int h[N], e[N], ne[N], idx;
int w[N], dist[N], st[N];
	
void add(int a,int b,int c)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void dijist()
{
	priority_queue<pII,vector<pII>,greater<pII>> heap;

	heap.push({0,1});
	
	dist[1] = 0;

	while(heap.size())
	{
		auto t = heap.top();heap.pop();
		if(st[t.second]) continue;
         else st[t.second] = 1;
		
		for(int i = h[t.second]; i != -1; i = ne[i])
		{
			int j = e[i];
			dist[j] = min(dist[j],dist[t.second] + w[i]);
			heap.push({dist[j],j});
		}
		
	}
}

void solve()
{
	int n, m;
	cin >> n >> m;
	
	memset(h,-1,sizeof h);
	memset(dist,0x3f,sizeof dist);

	while(m --)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}

	dijist();

	if(dist[n] == 0x3f3f3f3f) cout << -1 << endl;
	else cout << dist[n] << endl;
}

int main()
{
    solve();

	return 0;
}

bellman-ford 有边数限制的最短路

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
#include<iostream>
#include<cstring>

using namespace std;
const int N = 510, M = 10020;
struct{
	int a, b, c;

}edge[M];

int dist[N], last[N];

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0;i < m;i ++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edge[i] = {a, b, c};
	}
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0;

	for(int i = 0; i < k;i ++)
	{
		memcpy(last,dist,sizeof last);
		for(int j = 0;j < m;i ++)
		{
			auto e = edge[j];
			dist[e.b] = min(dist[e.b],last[e.a] + e.c);
		}
	}
	if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
	else cout << dist[n] << endl;
}

int main()
{
    solve();

	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
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int st[N], dist[N];
int n, m;

void add(int a,int b,int c)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx, w[idx ++] = c;
}

void spfa()
{
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	st[1] = 1;

	while(q.size())
	{
		int t = q.front();q.pop();
		st[t] = 0;

		for(int i = h[t];i != -1;i = ne[i])
		{
			int j = e[i];
			if(dist[j] > dist[t] + w[i])
			{
				dist[j] = dist[t] + w[i];
				if(!st[j])
				{
					q.push(j);
					st[j] = 1;
				}
			}
		}
	}
	
	if(dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
	else cout << dist[n] << endl;
}

void solve()
{
	memset(h,-1,sizeof h);
	memset(dist,0x3f,sizeof dist);
	
	cin >> n >> m;
	while(m --)
	{
		int a, b, c;
		cin >> a >> b >> c ;
		add(a, b, c);
	}
	
	spfa();
}

int main()
{
    solve();

	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
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstring>

using namespace std;

const int N = 530;
int book[N][N], st[N];
int n, m, dist[N];

int prim()
{
	int ans = 0;
	dist[1] = 0;
    
	for(int i = 0;i < n;i ++)
	{
		int t = -1;
		for(int j = 1;j <= n;j ++)
			if(!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;

		if(dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;

		ans += dist[t];
        
		st[t] = 1;
		
		for(int j = 1;j <= n;j ++) dist[j] = min(dist[j],book[t][j]);
	}

	return ans;
}

void solve()
{
	cin >> n >> m;

	memset(dist,0x3f,sizeof dist);
	memset(book,0x3f,sizeof book);

	while(m --)
	{
		int a, b, c;
		cin >> a >> b >> c;
		book[a][b] = book[b][a] = min(c,book[a][b]);
	}
	int ans = prim();

	if(ans == 0x3f3f3f3f) cout << "impossible" << endl;
	else cout << ans << endl; 

}

int main()
{
    solve();

	return 0;
}
Arithmetic
#算法
图论基础
http://example.com/2023/11/13/图论/
作者
smg
发布于
2023年11月13日
许可协议