最短路

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

板子题 注意几个点

1.dis数组的初始化 dis[s] = 0

2.整体的思路 最小堆的创建 尤其注意cmp函数 里面是大于不是小于

3.vis数组 在哪里更新

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int N = 5e5 + 10;
struct edges
{
	int to, w, next;
}edge[N];
int idx = 0;
int head[N];
inline void add(int from, int to, int w)
{
	edge[++idx].w = w;
	edge[idx].to = to;
	edge[idx].next = head[from];
	head[from] = idx;
}

struct Polar
{
	int dist, id;
	Polar(int dist, int id) : dist(dist), id(id) {};
};
struct cmp
{
	bool operator()(Polar a, Polar b)
	{
		return a.dist > b.dist;
	}
};
priority_queue<Polar, vector<Polar>, cmp> q;
long long dis[N];
int vis[N];
void dijkstra(int s)
{
	dis[s] = 0;
	q.push(Polar(0, s));
	while (!q.empty())
	{
		int p = q.top().id;
		q.pop();
		if (vis[p])
			continue;
		vis[p] = 1;
		for (int e = head[p]; e != 0; e = edge[e].next)
		{
			int to = edge[e].to, w = edge[e].w;

			dis[to] = min(dis[to], dis[p] + w);
			if (!vis[to])
				q.push(Polar(dis[to], to));
		}
	}
}
int main()
{
	int n, m, s;
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	for (int i = 1; i <= n; i++)dis[i] = 0x7fffffff;
	dijkstra(s);
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
}

P3385 【模板】负环 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

spfa板子 用spfa判负环

注意

1.一定一定一定非常注意 spfa函数的初始化 q.push 、dis inq inqc有没有初始化

2.每次如何更新inq inqc dis q

3.判负环 就是看inqc有没有>=n （同一个点的松弛次数）

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <queue>
const int N = 100010;
using namespace std;
struct edges
{
	int to, w, next;
};
edges edge[N];
int idx, head[N];
void add(int from, int to, int w)
{
	edge[++idx].to = to;
	edge[idx].w = w;
	edge[idx].next = head[from];
	head[from] = idx;
}
int dist[N];
int n, m;
void spfa(int s)
{
	int inq[N] = { 0 };
	
	queue<int>q;
	q.push(s);
	inq[s] = 1;
	dist[s] = 0;
	int inqc[N] = { 0 };
	inqc[s] = 1;
	
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		inq[p] = 0;
		for (int e = head[p]; e; e = edge[e].next)
		{
			int to = edge[e].to;
			if (dist[to] > dist[p] + edge[e].w)
			{
				dist[to] = dist[p] + edge[e].w;
				if (!inq[to])
				{
					inqc[to]++;
					if (inqc[to] >= n)
					{
						puts("YES");
						return ;
					}
					inq[to] = 1;
					q.push(to);
				}
			}
		}
	}
	puts("NO");
	return;
}
int main()
{
	int T = 0;
	cin >> T;
	while (T--)
	{
		
		cin >> n >> m;
		idx = 0;
		memset(head, 0, sizeof(head));
		memset(dist, 0x3f3f3f3f, sizeof(dist));
		for (int i = 0; i <= n; i++)
		{
			edge[i].to = 0;
			edge[i].next = 0;
		}
		for (int i = 0; i < m; i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
			if (w >= 0)add(v, u, w);
		}
		spfa(1);
	}
}

P5960 【模板】差分约束 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

差分约束
$$
\begin{cases} x_{c_1}-x_{c’1}\leq y_1 \x{c_2}-x_{c’2} \leq y_2 \ \cdots\ x{c_m} - x_{c’_m}\leq y_m\end{cases}
$$

类似于三角不等式 跟最短路的优化形式相近 考虑用最短路

变形 $x_{c1}\leq x_{c1}’ + y_1$ 即可以求最短路

添加一个超级源点 0 求出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
72
73
74
75
76
77
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, m;
struct edges
{
	int v, w, next;
}edge[10005];
int idx = 0;
int head[5005];
inline void add(int u, int v, int w)
{
	edge[++idx].v = v;
	edge[idx].w = w;
	edge[idx].next = head[u];
	head[u] = idx;
}
int vis[5005], tot[5005];
int dis[5005];
bool spfa(int s)
{
	queue<int>q;
	memset(dis, 0x3f3f3f3f, sizeof(dis));

	vis[s] = 1;
	dis[s] = 0;
	q.push(s);
	
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		vis[p] = 0;
		for (int e = head[p]; e; e = edge[e].next)
		{
			int to = edge[e].v, w = edge[e].w;
			if (dis[to] > dis[p] + w)
			{
				dis[to] = dis[p] + w;
				if (!vis[to])
				{

					vis[to] = 1;
					tot[to]++;
					if (tot[to] == n + 1)
					{
						return false;
					}
					q.push(to);
				}
			}
			
		}
	}
	return true;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		add(0, i, 0);
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	if (!spfa(0))cout << "NO" << endl;
	else
		for (int i = 1; i <= n; i++)
			cout << dis[i] << ' ';

	
}

P1993 小 K 的农场 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

差分约束变形

超级源点要初始化 连接0 到所有的点 权值为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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int m, n;

struct edges
{
	int w, v, next;
}edge[N];

int head[N], idx;

inline void add(int u, int v, int w)
{
	edge[++idx].v = v;
	edge[idx].w = w;
	edge[idx].next = head[u];
	head[u] = idx;
}

bool vis[5005];
int dis[5005], tot[5005];

bool spfa(int s)
{
	queue<int>q;
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	vis[s] = true;
	dis[s] = 0;
	q.push(s);
	tot[s]++;

	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		vis[p] = false;

		for (int e = head[p]; e; e = edge[e].next)
		{
			int to = edge[e].v, w = edge[e].w;
			if (dis[to] > dis[p] + w)
			{
				dis[to] = dis[p] + w;
				if (!vis[to])
				{
					vis[to] = true;
					tot[to]++;
					if (tot[to] == n + 1)
					{
						return false;
					}
					q.push(to);
				}
			}
		}
	}
	return true;
}

int main()
{
	cin >> n >> m;
	while (m--)
	{
		int c, u, v, w;
		cin >> c;
		if (c == 1)
		{
			cin >> u >> v >> w;
			add(u, v, -w);
		}
		else if (c == 2) 
		{
			cin >> u >> v >> w;
			add(v, u, w);
		}
		else if (c == 3)
		{
			cin >> u >> v;
			add(u, v, 0);
			add(v, u, 0);
		}
	}
	// 超级源点0
    for (int i = 1; i <= n; i++)
	{
		add(0, i, 0);
	}
	if (!spfa(0))cout << "No" << endl;
	else cout << "Yes" << endl;
}

B3611 【模板】传递闭包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

传递闭包 就和离散的传递闭包一个意思 如果存在a->b b->c 那就必须有a->c 就这样加上 注意这个题要用邻接矩阵存储

用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
35
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int g[1001][1001];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> g[i][j];
		}
	}
	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (g[k][j] && g[i][k])g[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << g[i][j] << " ";
		}
		cout << endl;
	}
}

P1144 最短路计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

无权图 可以用BFS 先到达的必定是最短的 用deg记录这个点dfs的层数 如果这个点的层数比上一个相邻结点多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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, m;
const int N = 1e6 + 7;
vector<int>g[N];
int deg[N], cnt[N], vis[N];
void bfs()
{
	queue<int>q;
	q.push(1);
	cnt[1] = 1;
	deg[1] = 0;
	vis[1] = 1;
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		for (auto e : g[p])
		{
			if (!vis[e])
			{
				vis[e] = 1;
				q.push(e);
				deg[e] = deg[p] + 1;
			}
			if (deg[e] == deg[p] + 1)
				cnt[e] = (cnt[e] + cnt[p]) % 100003;
			
		}
	}
	for (int i = 1; i <= n; i++)
		cout << cnt[i] << endl;
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	bfs();
}

P1462 通往奥格瑞玛的道路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

神奇的二分+最短路

一开始题目看不懂 求可以到达的情况下 他所经过的所有城市中 收费最多的一次 收取的费用的最小值是多少

就是要最小化 （经过城市收费的最大值）

最大（小）化 最小（大）值 就用二分

二分钱数 check就找可以通过并且通过的钱数小于mid 的

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int n, m, b;
const int N = 1e5 + 7;
int f[N];
struct edges
{
	int to, w, next;
}edge[N];
int idx, head[N];
inline void add(int from, int to, int w)
{
	edge[++idx].w = w;
	edge[idx].to = to;
	edge[idx].next = head[from];
	head[from] = idx;
}
struct Polar
{
	int id, dis;
	Polar(int dis, int id) :dis(dis), id(id) {}
};
struct cmp
{
	bool operator ()(Polar a, Polar b)
	{
		return a.dis > b.dis;
	}
};
int dis[N];
int vis[N];
bool dij(int mid)
{
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	priority_queue<Polar, vector<Polar>, cmp>q;
	q.push({ 0, 1 });
	dis[1] = 0;
	if (f[1] > mid)return false;
	while (!q.empty())
	{
		int p = q.top().id;
		q.pop();
		if (vis[p])continue;
		vis[p] = 1;
		for (int e = head[p]; e; e = edge[e].next)
		{
			int to = edge[e].to;
			if (f[to] > mid)continue;
			if (dis[to] > dis[p] + edge[e].w)
			{
				dis[to] = dis[p] + edge[e].w;
				q.push({ dis[to], to });
			}
		}
	}
	if (dis[n] > b)return false;
	else return true;
}

int main()
{
	cin >> n >> m >> b;
	int l = 0, r = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> f[i];
		r = max(f[i], r);
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	if (!dij(INT_MAX))
	{
		cout << "AFK" << endl;
		return 0;
	}
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (dij(mid))
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << l << endl;
}

[P6464 传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思考优化策略 从$O(n^5)$优化到$O(n^4)$

最初的想法应该是 每两个点为0都单独($O(n^2)$)再跑一遍Floyd($O(n^3)$)

但是其实不需要 而是只需要更新{加入传送门之后 距离改变了 }会影响到的那几条边 假设与l—b加上传送门 只用更新 需要中介l的点和需要中介b 的点即可

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
int f[110][110];
int g[110][110];
int main()
{
	int n, m;
	cin >> n >> m;
	memset(f, 0x3f3f3f3f, sizeof(f));
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		f[u][v] = f[v][u] = w;
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++) 
		{
			for (int j = 1; j <= n; j++)
			{
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
				g[i][j] = f[i][j];
			}
		}
	}

	int ans = 2e9 + 7;
	for (int l = 1; l <= n; l++)
	{
		for (int b = 1; b < l; b++)
		{
			
			g[l][b] = g[b][l] = 0;
			// 关键优化步骤
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
				}
			}
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					g[i][j] = min(g[i][j], g[i][b] + g[b][j]);
				}
			}
			int ret = 0;
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j < i; j++)
				{
					ret += g[i][j];
				}
			}
			ans = min(ans, ret);
			memcpy(g, f, sizeof(f));
		}
	}
	cout << ans;
}

[P2419 USACO08JAN] Cow Contest S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

关键在于 能够确定排名的牛 是怎么看的

能确定排名 就是直到有几只牛比他高 有几只牛比他低 用有向图表示 弧尾表示赢的牛 弧头表示输的牛

那么入度就是输给几头牛的数 出度就是赢了几头牛 当入度+出度=n-1的时候 代表他已经确定和其他n - 1头牛的关系了 说明可以排名

入度和出度 可以用bfs 正反图+dfs（因为间接赢也是赢）来求

也可以用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
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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
/*
* 胜利者指向失败者
* 入度是被多少牛打败
* 出度是打败了多少牛
* 能确定排名就是 入度 + 出度 = n - 1
*/
const int N = 1e5;
vector<int>g[N], rg[N];
int win[N], lose[N];
int win_c, lose_c;

void dfs_win(int i)
{
	for (auto y : g[i])
		if (!win[y])
		{
			win[y] = 1;
			win_c++;
			dfs_win(y);
		}
}
void dfs_lose(int i)
{
	for (auto y : rg[i])
		if (!lose[y])
		{
			lose[y] = 1;
			lose_c++;
			dfs_lose(y);
		}
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		rg[v].push_back(u);

	}
	int ret = 0;
	for (int i = 1; i <= n; i++)
	{
		win_c = lose_c = 0;
		memset(win, 0, sizeof(win));
		memset(lose, 0, sizeof(lose));
		dfs_win(i);
		dfs_lose(i);
		//cout << win_c << lose_c << endl;
		if (win_c + lose_c == n - 1)ret++;
	}
	cout << ret;
}

[P1073 NOIP2009 提高组] 最优贸易 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

由于边权为1 考虑BFS

权值在点上 可以预处理出一个中转点i i满足通路 1~i i ~ n （即首先需要能够到达n才行）

然后再1i上找一个点买入 in找一个点卖出 则可以用两次bfs求出1i的每个点的最小值 in的每个点的最大值 （求in可以存反图 求ni的点 然后求与1~i 的交集）

最后遍历1~n 即令每个点都为中转点 求出哪个点作为中转时最大

注意 1 和n 作为中转也可以 要给1和n赋初值 当重复经过的时候也必须算上 就是说BFS的vis即使已经为1 maxn和minn也要进行比较赋值

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 6e5 + 10;
int mon[N];
vector<int>G[N];
vector<int>rg[N];
bool vis[N];
int maxn[N], minn[N];

void bfs1(int u)
{
	queue<int>q;
	q.push(u);
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		for (auto v : G[p])
		{
			if (!vis[v])
			{
				q.push(v);
				vis[v] = 1;
				
			}
			minn[v] = min(minn[p], mon[v]);
		}
	}
}
void bfs2(int u)
{
	queue<int>q;
	q.push(u);
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		for (auto v : rg[p])
		{
			if (!vis[v])
			{
				q.push(v);
				vis[v] = 1;
				
			}
			maxn[v] = max(maxn[p], mon[v]);
		}
	}
}

int main()
{
	int n, m;
	int ret = 0;
	cin >> n >> m;
	memset(maxn, -1, sizeof(maxn));
	memset(minn, 10, sizeof(minn));
	for (int i = 1; i <= n; i++)
	{
		cin >> mon[i];
	}
	for (int i = 0; i < m; i++)
	{
		int u, v, t;
		cin >> u >> v >> t;
		rg[v].push_back(u);
		G[u].push_back(v);

		if (t > 1)
		{
			G[v].push_back(u);
			rg[u].push_back(v);
		}
	}
	minn[1] = maxn[1] = mon[1];
	maxn[n] = minn[n] = mon[n];
	bfs1(1);
	memset(vis, 0, sizeof(vis));
	bfs2(n);
	for (int i = 1; i <= n; i++)
	{
		//cout << minn[i] << " " << maxn[i] << endl;
		ret = max(ret, maxn[i] - minn[i]);
	}
	cout << ret << endl;
	return 0;
}
algorithm
#algorithm #Ans #graph
最短路
https://brtulien.github.io/2023/11/25/最短路/
作者
Brtulien
发布于
2023年11月25日
更新于
2024年7月1日
许可协议