图论复习（最短路、最小生成树）

图论复习

拓扑排序

原题链接：AcWing 848. 有向图的拓扑序列 - AcWing

在建图时，记录每个节点的入度，首先把入度为0的点都存到队列里。

然后在搜索时，每搜到一个点，就把这个点的入度 -1 ，当它的入度变为0时，就把它存到队列里。直到队列里全部的点都搜索完。

这时要判断一下是否所有的点的入度都为0了。如果是，那么就找到了一个拓扑序列；否则就没有找到。

#include<bits/stdc++.h>

using namespace std;
const int N = 3e5;
int h[N], e[N], ne[N], w[N], idx;
int n, m;
int d[N];
int q[N];
int hh = 0, tt = -1;
	
void add(int a, int b)
{
	e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

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

	for (int i = 1; i <= n; i++)
	{
    	if(d[i]!=0)
        {
            cout<<-1<<endl;
            return;
        }
	}
	
	for(int i = 0;i<n;i++)
	    cout<<q[i]<<" ";
	
}
int main()
{
	int a, b;
	cin >> n >> m;
	memset(h,-1,sizeof h);
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b;
		add(a, b);
 		d[b]++;	//入度+1
	}

	int k;
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
		    q[++tt]=i;
		}
	}
	bfs();
	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
62
63
64
65
66
67

dijkstra算法 堆优化

原题链接：850. Dijkstra求最短路 II - AcWing题库

利用优先队列优化dijkstra算法。注意优先队列的定义方式（默认为大根堆，而求最短路要使用小根堆）

priority_queue<int,vector<int>,less<int> > q;	//默认形式，大根堆
priority_queue<int,vector<int>,greater<int> > q;	//大根堆形式
1
2

下面展示dijkstra(用结构体定义的优先队列)

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5, M = 4e5;
int h[N], e[M], ne[M],w[M], idx;
int n, m;
int dist[N];

struct node
{
	int dist;
	int id;

	bool operator < (const node& t)const	//默认大根堆，所以要用大于号重载小于号
	{
		if (dist == t.dist)
			return id > t.id;
		return dist > t.dist;
	}
};
node p[N];
priority_queue<node> q;
bool st[N];

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

void dijkstra(int k)
{
	memset(dist, 0x3f, sizeof dist);
	dist[k] = 0;
	q.push({ 0,1 });
	while (!q.empty())
	{
		auto t = q.top();
		q.pop();
		if (st[t.id] == true)
			continue;
		st[t.id] = true;
		for (int i = h[t.id]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[t.id] + w[i])
			{
				dist[j] = dist[t.id] + w[i];
				q.push({ dist[j],j });
			}
		}
	}

	if (dist[n] > 0x3f3f3f3f / 2)
		cout << -1 << endl;
	else
		cout << dist[n] << endl;
	return;
}
int main()
{
	int a, b, c;
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		add(a, b, c);
	}
	dijkstra(1);
	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
62
63
64
65
66
67
68
69
70
71

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

原题链接：853. 有边数限制的最短路 - AcWing题库

#include<bits/stdc++.h>

using namespace std;
const int M = 1e5;
int n, m, k;
struct node
{
	int a, b, c;
};
node p[M];
int dist[M], backup[M];

void bellman()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	for (int i = 0; i < k; i++)
	{
		memcpy(backup, dist, sizeof dist);
		for (int j = 0; j < m; j++)
		{
		    auto e=p[j];
			if (dist[e.b] > backup[e.a] + e.c)
			{
				dist[e.b] = backup[e.a] + e.c;

			}
            // dist[e.b] = min(dist[e.b] ,backup[e.a]+e.c);
		}
	}
	if (dist[n] > 0x3f3f3f3f / 2)
		cout << "impossible";
	else
		cout << dist[n];
}
int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++)
	{
	    int a,b,c;
	    cin>>a>>b>>c;
	    p[i]={a,b,c};
// 		cin >> p[i].a >> p[i].b >> p[i].c;
	}
	bellman();
	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

SPFA算法（最短路、求负环）

原题链接：851. spfa求最短路 - AcWing题库

思路分析

spfa算法适用于在有负权的图中求最短路的问题。

spfa 于 dijkstra的区别主要有两点

• 数据结构的使用：dijkstra使用优先队列，而spfa使用普通的队列即可
• st[]数组的目的不同：dijkstra的st[]是记录每个点是否已经搜过了。而spfa的st[]则记录的是该点是否在队列中。

#include<bits/stdc++.h>

using namespace std;
const int N = 3e5;
int h[N], ne[N], e[N], w[N], idx;
int n, m;
queue<int> q;
int dist[N];
bool st[N];

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

void spfa()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	q.push(1);
	st[1] = true;
	
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		for (int i = h[t]; ~i; 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]=true;
				}
			}
		}
	}

	if (dist[n] > 0x3f3f3f3f / 2)
		cout << "impossible";
	else
		cout << dist[n];
}

int main()
{
	int a, b, c;
	memset(h,-1,sizeof h);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		add(a, b, c);
	}
	spfa();
	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

原题链接：852. spfa判断负环 - AcWing题库

思路分析

怎么判断是否存在负环？

需要设置一个新的数组cnt[]，用来记录在最短路中所经过的边的数量。

如果存在一个cnt[j]，使得它大于 n ，也就是说，此时肯定存在一个多余的边——也就是形成了环。又因为在求最短路的过程中，满足条件的dist[]是不断更新变小的，所以存在一个可以使最短路不断变小的环——也就是 负环！

#include<bits/stdc++.h>

using namespace std;
const int N = 3e5;
int h[N], ne[N], e[N], w[N], idx;
int n, m;
queue<int> q;
int dist[N],cnt[N];
bool st[N];

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

bool spfa()
{
	memset(dist, 0x3f, sizeof dist);	//因为我们并不关心最短路的大小，所以这里初始化可以随意设置
	for (int i = 1; i <= n; i++)	//这里是把所有的节点都先放到队列里。因为如果只放q.push(1)，意思就是寻找 节点1到其余所有节点的最短路中是否存在负环。但是题目是有向边，所以要考虑所有节点到其他所有节点的最短路中是否存在有向边。
	{
		st[i] = true;
		q.push(i);
	}

	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		for (int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[t] + w[i])
			{
				dist[j] = dist[t] + w[i];
				cnt[j] = cnt[t] + 1;	//边数+1，判断是否存在负环。
				if (cnt[j] >= n)	
					return true;
				if (!st[j])	//如果不在队列里面，就把它放到队列里去。
				{
					st[j] = true;
					q.push(j);
				}
			}
		}
	}
	return false;
}

int main()
{
	int a, b, c;
	cin >> n >> m;
	memset(h,-1,sizeof h);
	
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		add(a, b, c);
	}
	if (spfa())
		cout << "Yes\n";
	else
		cout << "No\n";
	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
62
63
64
65
66

Floyd算法——多源最短路

原题链接：854. Floyd求最短路 - AcWing题库

思路分析

利用了dp的思想。

如果要求点i到点j的最短距离dist[i][j]，如果要更新dist[i][j] 那么就要用到另一个中间点k，即：dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]) 。

而对于任意两点i , j以及这个中间节点 k 。它们的取值范围都是1–n的。

那么可以用如下for循环表示：

for (int k = 1; k <= n; k++)	//中间节点k放在for循环的最外面，表示首先考虑节点1作为中间节点时，所有节点的最短路径。然后再通过节点2 3 4 ... 作为中间节点。
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10

整体代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
int dist[N][N];
int n, m, l;

void floyd()
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
}
int main()
{
	cin >> n >> m >> l;
	memset(dist, 0x3f, sizeof dist);
	for(int i = 1;i<=n;i++)		//注意节点到自身的距离初始化为0
	    dist[i][i]=0;
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		dist[a][b] = min(dist[a][b],c);	//因为要求最小值，所以要记录最小值（处理重边）
	}

	floyd();
	for (int i = 1; i <= l; i++)
	{
		int a, b;
		cin >> a >> b;
		if (dist[a][b] > 0x3f3f3f3f / 2)
			cout << "impossible\n";
		else
			cout << dist[a][b] << "\n";
	}
	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

Prim算法求最小生成树

原题链接：858. Prim算法求最小生成树 - AcWing题库

思路分析

首先应该知道，Prim算法求最小生成树，适用于稠密图，故直接用邻接矩阵来存储。

Prim的算法思想和dijkstra很像。

dijkstra的思想是：

• 建立一个dist[]表示每个点距离起点的最短路径，并将其初始化为0x3f（起点初始化为0）

• 利用bool数组st[]记录点是否在集合里（最短路里面）

• 找到集合外的 距离起点最近的点，并用它更新其他点到起点的距离

而prim的思想是：

• 找到集合外的 距离集合最近的点，并用它更新其他点到该集合的距离 （这里的集合是指生成树）

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;

int g[N][N];
int n, m;
int dist[N];
int pre[N];	//用于记录前置节点，可以打印输出路径
bool st[N];
int res;

void prim()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;	//假如从第一个节点开始，来生成最小生成树（注意这里从哪个节点开始并不影响）
	for (int i = 1; i <= n; i++)	//寻找每个节点
	{
		int t = -1;
		for (int j = 1; j <= n; j++)	//找到一个在集合外，并且距离集合最近的节点
		{
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		}	
        cout<<t<<endl;
        //如果找不到这个点，就输出不可能
		if (dist[t] == 0x3f3f3f3f)
		{
			cout << "impossible";
			return;
		}
		st[t] = true;	//找到点就把它加入到集合里面去
		res += dist[t];	//更新最短路的距离，注意这里的距离要放在dist[t]更新之前，因为有可能会有自环的情况，导致dist变小，但是自环并不能生成树
		
        //用该节点更新其他节点到集合的距离
		for (int j = 1; j <= n; j++)
		{
			if (dist[j] > g[t][j] && !st[j])
			{
				dist[j] = g[t][j];
				pre[j] = t;	//更新前置节点
			}
		}
	}
	cout << res;
}

int main()
{
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= n; i++)
		g[i][i] = 0;
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	prim();
	
// 	for(int i = n;i>=1;i--)
// 	{
// 	    cout<<endl<<i<< ' '<<pre[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
54
55
56
57
58
59
60
61
62
63
64
65
66
67

Kruskal算法求最小生成树

原题链接：859. Kruskal算法求最小生成树 - AcWing题库

思路分析

kruskal算法是按照边的大小来构建生成树的，具体思路如下：

• 首先把所有的边按照权重从小到大的顺序排序

• 接着把在集合（生成树）之外的边，按照顺序依次添加进去 （利用并查集，快速的判断是否在集合内）

• 如果最终集合里边的数量，恰好为点n的数量减一，那么就生成成功了。

代码如下

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
struct node
{
	int a, b, c;
	bool operator< (const node& t)const	//重载小于号，按照权重从小到大的顺序排序
	{
		return c < t.c;
	}
};

node p[N];
int n, m;
int fa[N];	//记录父节点
int res;	//是最小生成树的权重之和
int cnt;	//记录进入生成树的边的数量，用与判断是否生成成功

int find(int x)	//并查集
{
	if (fa[x] != x)	//如果该节点的父节点不是他自己（也就是说它不是祖先节点），
		fa[x] = find(fa[x]);	//那么就递归查询它的父节点
	return fa[x];	//最终返回它的父节点
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		p[i] = { a,b,c };
	}
	sort(p + 1, p + 1 + m);

	for (int i = 1; i <= n; i++)	//并查集要初始化！每个节点的最初的父节点都是自己
		fa[i] = i;

	for (int i = 1; i <= m; i++)
	{
		int a = p[i].a, b = p[i].b, c = p[i].c;
		a = find(a), b = find(b);	//分别找到这条边的两个端点的父节点
		if (a != b)	//如果这两个点不属于同一个父节点，也就是说这条边不在集合里
		{
			fa[a] = b;	//把集合a并入到b里去
			res += c;	//更新权重
			cnt++;		//更新边数
		}
	}
	if (cnt == n - 1)
	{
		cout << res;
	}
	else
		cout << "impossible\n";
	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