今天我刷题了吗
搜索文档…
SPFA 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const ll _inf(0x3f3f3f3f3f3f3f3f);
9
const int mod(1e9 + 7);
10
const int maxn(1e4 + 10);
11
const int maxm(5e5 + 10);
12
int ecnt, head[maxn];
13
ll dis[maxn];
14
bool vis[maxn];
15
16
struct edge {
17
int to, wt, nxt;
18
} edges[maxm];
19
20
template<typename T = int>
21
inline const T read()
22
{
23
T x = 0, f = 1;
24
char ch = getchar();
25
while (ch < '0' || ch > '9') {
26
if (ch == '-') f = -1;
27
ch = getchar();
28
}
29
while (ch >= '0' && ch <= '9') {
30
x = (x << 3) + (x << 1) + ch - '0';
31
ch = getchar();
32
}
33
return x * f;
34
}
35
36
template<typename T>
37
inline void write(T x, char c)
38
{
39
if (x < 0) {
40
putchar('-');
41
x = -x;
42
}
43
if (x > 9) write(x / 10, false);
44
putchar(x % 10 + '0');
45
if (c) putchar(c);
46
}
47
48
void addEdge(int u, int v, int w)
49
{
50
edges[ecnt].to = v;
51
edges[ecnt].wt = w;
52
edges[ecnt].nxt = head[u];
53
head[u] = ecnt++;
54
}
55
56
void spfa(int src)
57
{
58
queue<int> q;
59
q.push(src);
60
dis[src] = 0;
61
vis[src] = true;
62
while (not q.empty()) {
63
int u = q.front();
64
q.pop();
65
vis[u] = false;
66
for (int i = head[u]; ~i; i = edges[i].nxt) {
67
int v = edges[i].to, w = edges[i].wt;
68
if (dis[v] > dis[u] + w) {
69
dis[v] = dis[u] + w;
70
if (not vis[v]) {
71
q.push(v);
72
vis[v] = true;
73
}
74
}
75
}
76
}
77
}
78
79
int main()
80
{
81
#ifdef ONLINE_JUDGE
82
#else
83
freopen("input.txt", "r", stdin);
84
#endif
85
memset(head, -1, sizeof head);
86
memset(dis, 0x3f, sizeof dis);
87
int n = read(), m = read(), s = read();
88
while (m--) {
89
int u = read(), v = read(), w = read();
90
addEdge(u, v, w);
91
}
92
spfa(s);
93
for (int i = 1; i <= n; ++i) {
94
write(dis[i] == _inf ? INT_MAX : dis[i], i == n ? '\n' : ' ');
95
}
96
return 0;
97
}
Copied!
SPFA 已死
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const ll _inf(0x3f3f3f3f3f3f3f3f);
9
const int mod(1e9 + 7);
10
const int maxn(1e5 + 10);
11
const int maxm(2e5 + 10);
12
int ecnt, head[maxn];
13
ll dis[maxn];
14
bool vis[maxn];
15
16
struct edge {
17
int to, wt, nxt;
18
} edges[maxm];
19
20
template<typename T = int>
21
inline const T read()
22
{
23
T x = 0, f = 1;
24
char ch = getchar();
25
while (ch < '0' || ch > '9') {
26
if (ch == '-') f = -1;
27
ch = getchar();
28
}
29
while (ch >= '0' && ch <= '9') {
30
x = (x << 3) + (x << 1) + ch - '0';
31
ch = getchar();
32
}
33
return x * f;
34
}
35
36
template<typename T>
37
inline void write(T x, char c)
38
{
39
if (x < 0) {
40
putchar('-');
41
x = -x;
42
}
43
if (x > 9) write(x / 10, false);
44
putchar(x % 10 + '0');
45
if (c) putchar(c);
46
}
47
48
void addEdge(int u, int v, int w)
49
{
50
edges[ecnt].to = v;
51
edges[ecnt].wt = w;
52
edges[ecnt].nxt = head[u];
53
head[u] = ecnt++;
54
}
55
56
void spfa(int src)
57
{
58
queue<int> q;
59
q.push(src);
60
dis[src] = 0;
61
vis[src] = true;
62
while (not q.empty()) {
63
int u = q.front();
64
q.pop();
65
vis[u] = false;
66
for (int i = head[u]; ~i; i = edges[i].nxt) {
67
int v = edges[i].to, w = edges[i].wt;
68
if (dis[v] > dis[u] + w) {
69
dis[v] = dis[u] + w;
70
if (not vis[v]) {
71
q.push(v);
72
vis[v] = true;
73
}
74
}
75
}
76
}
77
}
78
79
int main()
80
{
81
#ifdef ONLINE_JUDGE
82
#else
83
freopen("input.txt", "r", stdin);
84
#endif
85
memset(head, -1, sizeof head);
86
memset(dis, 0x3f, sizeof dis);
87
int n = read(), m = read(), s = read();
88
while (m--) {
89
int u = read(), v = read(), w = read();
90
addEdge(u, v, w);
91
}
92
spfa(s);
93
for (int i = 1; i <= n; ++i) {
94
write(dis[i] == _inf ? INT_MAX : dis[i], i == n ? '\n' : ' ');
95
}
96
return 0;
97
}
Copied!
tql
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(1e5 + 10);
10
const int maxm(1e6 + 10);
11
int ecnt, head[maxn];
12
int dis[maxn];
13
bool vis[maxn];
14
deque<int> q;
15
16
struct edge {
17
int to, wt, nxt;
18
} edges[maxm];
19
20
template<typename T = int>
21
inline const T read()
22
{
23
T x = 0, f = 1;
24
char ch = getchar();
25
while (ch < '0' || ch > '9') {
26
if (ch == '-') f = -1;
27
ch = getchar();
28
}
29
while (ch >= '0' && ch <= '9') {
30
x = (x << 3) + (x << 1) + ch - '0';
31
ch = getchar();
32
}
33
return x * f;
34
}
35
36
template<typename T>
37
inline void write(T x, char c)
38
{
39
if (x < 0) {
40
putchar('-');
41
x = -x;
42
}
43
if (x > 9) write(x / 10, false);
44
putchar(x % 10 + '0');
45
if (c) putchar(c);
46
}
47
48
void addEdge(int u, int v, int w)
49
{
50
edges[ecnt].to = v;
51
edges[ecnt].wt = w;
52
edges[ecnt].nxt = head[u];
53
head[u] = ecnt++;
54
}
55
56
void swap_slf()
57
{
58
if (q.size() > 2 and dis[q.front()] > dis[q.back()]) {
59
swap(q.front(), q.back());
60
}
61
}
62
63
void spfa(int src)
64
{
65
dis[src] = 0;
66
q.push_back(src);
67
vis[src] = true;
68
while (not q.empty()) {
69
int u = q.front();
70
q.pop_front();
71
swap_slf();
72
vis[u] = false;
73
for (int i = head[u]; compl i; i = edges[i].nxt) {
74
int v = edges[i].to, w = edges[i].wt;
75
if (dis[v] > dis[u] + w) {
76
dis[v] = dis[u] + w;
77
if (not vis[v]) {
78
q.push_back(v);
79
swap_slf();
80
vis[v] = true;
81
}
82
}
83
}
84
}
85
}
86
87
int main()
88
{
89
#ifdef ONLINE_JUDGE
90
#else
91
freopen("input.txt", "r", stdin);
92
#endif
93
memset(head, -1, sizeof head);
94
memset(dis, 0x3f, sizeof dis);
95
int n = read(), m = read(), s = read();
96
while (m--) {
97
int u = read(), v = read(), w = read();
98
addEdge(u, v, w);
99
}
100
spfa(s);
101
for (int i = 1; i <= n; ++i) {
102
if (dis[i] == inf) {
103
puts("NO PATH");
104
} else {
105
write(dis[i], i == n ? 10 : 32);
106
}
107
}
108
return 0;
109
}
Copied!
判断存在负环的条件:1、当前点入列达到
nn
次;2、源点到当前点的最短(长)路径达到
nn
两种玄学优化:1、入列计数 tot >= n * 2 跳出;2、使用 stack 代替 queue
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const ll _inf(0x3f3f3f3f3f3f3f3f);
9
const int mod(1e9 + 7);
10
const int maxn(2e3 + 10);
11
const int maxm(3e3 + 10);
12
bool vis[maxn];
13
int ecnt, head[maxn], cnt[maxn], dis[maxn];
14
15
struct edge {
16
int to, wt, nxt;
17
} edges[maxm << 1];
18
19
template<typename T = int>
20
inline const T read()
21
{
22
T x = 0, f = 1;
23
char ch = getchar();
24
while (ch < '0' || ch > '9') {
25
if (ch == '-') f = -1;
26
ch = getchar();
27
}
28
while (ch >= '0' && ch <= '9') {
29
x = (x << 3) + (x << 1) + ch - '0';
30
ch = getchar();
31
}
32
return x * f;
33
}
34
35
template<typename T>
36
inline void write(T x, char c)
37
{
38
if (x < 0) {
39
putchar('-');
40
x = -x;
41
}
42
if (x > 9) write(x / 10, false);
43
putchar(x % 10 + '0');
44
if (c) putchar(c);
45
}
46
47
void addEdge(int u, int v, int w)
48
{
49
edges[ecnt].to = v;
50
edges[ecnt].wt = w;
51
edges[ecnt].nxt = head[u];
52
head[u] = ecnt++;
53
}
54
55
bool spfa(int tot)
56
{
57
queue<int> q;
58
vis[1] = true;
59
dis[1] = 0;
60
q.push(1);
61
while (not q.empty()) {
62
int u = q.front();
63
q.pop();
64
vis[u] = false;
65
for (int i = head[u]; ~i; i = edges[i].nxt) {
66
int v = edges[i].to, w = edges[i].wt;
67
if (dis[v] > dis[u] + w) {
68
dis[v] = dis[u] + w;
69
if (not vis[v]) {
70
cnt[v] = cnt[u] + 1;
71
if (cnt[v] >= tot) {
72
return true;
73
}
74
vis[v] = true;
75
q.push(v);
76
}
77
}
78
}
79
}
80
return false;
81
}
82
83
int main()
84
{
85
#ifdef ONLINE_JUDGE
86
#else
87
freopen("input.txt", "r", stdin);
88
#endif
89
int t = read();
90
while (t--) {
91
ecnt = 0;
92
memset(head, -1, sizeof head);
93
memset(dis, 0x3f, sizeof dis);
94
memset(vis, false, sizeof vis);
95
memset(cnt, 0, sizeof cnt);
96
int n = read(), m = read();
97
while (m--) {
98
int u = read(), v = read(), w = read();
99
addEdge(u, v, w);
100
if (w >= 0) {
101
addEdge(v, u, w);
102
}
103
}
104
printf("%s\n", spfa(n) ? "YES" : "NO");
105
}
106
return 0;
107
}
Copied!
差分约束:求最小值→最长路,求最大值→最短路
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(5e3 + 10);
10
const int maxm(1e4 + 10);
11
bool vis[maxn];
12
int ecnt, head[maxn], cnt[maxn], dis[maxn];
13
14
struct edge {
15
int to, wt, nxt;
16
} edges[maxm];
17
18
template<typename T = int>
19
inline const T read()
20
{
21
T x = 0, f = 1;
22
char ch = getchar();
23
while (ch < '0' || ch > '9') {
24
if (ch == '-') f = -1;
25
ch = getchar();
26
}
27
while (ch >= '0' && ch <= '9') {
28
x = (x << 3) + (x << 1) + ch - '0';
29
ch = getchar();
30
}
31
return x * f;
32
}
33
34
template<typename T>
35
inline void write(T x, char c)
36
{
37
if (x < 0) {
38
putchar('-');
39
x = -x;
40
}
41
if (x > 9) write(x / 10, false);
42
putchar(x % 10 + '0');
43
if (c) putchar(c);
44
}
45
46
void addEdge(int u, int v, int w)
47
{
48
edges[ecnt].to = v;
49
edges[ecnt].wt = w;
50
edges[ecnt].nxt = head[u];
51
head[u] = ecnt++;
52
}
53
54
bool spfa(int n)
55
{
56
memset(dis, 0x3f, sizeof dis);
57
dis[0] = 0;
58
queue<int> q;
59
q.push(0);
60
vis[0] = true;
61
while (not q.empty()) {
62
int u = q.front();
63
q.pop();
64
vis[u] = false;
65
for (int i = head[u]; compl i; i = edges[i].nxt) {
66
int v = edges[i].to, w = edges[i].wt;
67
if (dis[v] > dis[u] + w) {
68
dis[v] = dis[u] + w;
69
if (not vis[v]) {
70
vis[v] = true;
71
q.push(v);
72
cnt[v] = cnt[u] + 1;
73
if (cnt[v] >= n + 1) {
74
return false;
75
}
76
}
77
}
78
}
79
}
80
return true;
81
}
82
83
int main()
84
{
85
#ifdef ONLINE_JUDGE
86
#else
87
freopen("input.txt", "r", stdin);
88
#endif
89
ios::sync_with_stdio(false);
90
memset(head, -1, sizeof head);
91
int n = read(), m = read();
92
while (m--) {
93
int u = read(), v = read(), w = read();
94
addEdge(v, u, w);
95
}
96
for (int i = 0; i <= n; ++i) {
97
addEdge(0, i, 0);
98
}
99
if (spfa(n)) {
100
for (int i = 1; i <= n; ++i) {
101
write(dis[i], " \n"[i == n]);
102
}
103
} else {
104
printf("NO\n");
105
}
106
return 0;
107
}
Copied!
最近更新 1yr ago
复制链接