Cpp算法-图论-欧拉回路

邻接矩阵

说明

G[][]邻接矩阵

deg[]

ans[]欧拉回路

n, e点数、边数

实现

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
int G[maxn][maxn], deg[maxn], ans[maxn];
int n, e, x, y, ansi, s;

void Euler(int i)
{
for (int j = 1; j <= n; ++j)
{
if (G[i][j])
{
G[i][j] = G[j][i] = 0;
Euler(j);
}
}
ans[++ansi] = i;
}

int main()
{
scanf("%d %d", &n, &e);
for (int i = 1; i <= e; ++i)
{
scanf("%d %d", &x, &y);
G[x][y] = G[y][x] = 1;
deg[x]++;
deg[y]++;
}
s = 1;
for (int i = 1; i <= n; ++i)
if (deg[i] % 2 == 1)
s = i;
Euler(s);
for (int i = 1; i <= ansi; ++i)
printf("%d ", ans[i]);
printf("\n");
return 0;
}

链式前向星

说明

n, m点数、边数

head, edge[]链式前向星

ans[], ansi路径、数组大小

vis[]记录

make()建图

实现

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
int head[maxn];
struct Node
{
int to, next;
}edge[maxm];

void make()
{
scanf("%d %d", &n, &m);
for (int k = 1; k <= m; ++k)
{
int i, j;
scanf("%d %d", &i, &j);
edge[k].to = i;
edge[k].next = head[i];
head[i] = k;
}
return;
}

int ans[maxm];
int ansi = 0;
bool vis[2 * maxm];

void dfs(int now)
{
for (int k = head[now]; k != 0; k = edge[k].next)
{
if (!vis[k])
{
vis[k] = true;
vis[k ^ 1] = true;
dfs(edge[k].to);
ans[ansi++] = k;
}
}
}

Cpp算法-动态规划

待完成

多阶段过程决策的最优化问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
graph LR
A --5--> B1
A --3--> B2
B1 --1--> C1
B1 --6--> C2
B1 --3--> C3
B2 --8--> C2
B2 --4--> C4
C1 --5--> D1
C1 --6--> D2
C2 --5--> D1
C3 --8--> D3
C4 --3--> D3
D1 --3--> E
D2 --4--> E
D3 --3--> E

!!! tldr “题目及注解”
求上图从 $A$ 到 $E$ 的最短距离


$K$: 阶段

$D(X_I, (X+1)_J)$: 从 $X_I$ 到 $(X+1)_J$ 的距离

$F_K(X_I)$: $K$ 阶段下 $X_I$ 到终点 $E$ 的最短距离

倒推:
$$
K=4\qquad F_4(D_1)=3\qquad F_4(D_2)=4\qquad F_4(D_3)=3
$$
$$
K=5\qquad F_3(C_1)=min(D(C_1,D_1)+F_4(D_1),D(C_1,D_2)+F_4(D_2))=min(5+3,6+4)=8
F_3(C_2)
$$

Cpp算法-图论-Dijkstra

说明

n, m点数、边数

G[][]邻接矩阵存图

dist[]路径长度

pre[]路径

make()建图

实现

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
const int maxn = 10010;
int n, m, G[maxn][maxn], dist[maxn], pre[maxn], s;

void make()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
G[i][j] = INT_MAX;
for (int i = 1; i <= n; ++i) G[i][i] = 0;
for (int i = 1; i <= m; ++i)
{
int from, to, w;
scanf("%d %d %d", &from, &to, &w);
G[from][to] = w;
}
return;
}

void Dijkstra()
{
int k, min;
bool p[maxn];
for (int i = 1; i <= n; ++i)
{
p[i] = false;
if (i != s)
{
dist[i] = G[s][i];
pre[i] = s;
}
}
dist[s] = 0; p[s] = true;
for (int i = 1; i <= n - 1; ++i)
{
min = INT_MAX; k = 0;
for (int j = 1; j <= n; ++j)
{
if (!p[j] && dist[j] < min)
{
min = dist[j];
k = j;
}
}
if (k == 0) return;
p[k] = true;
for (int j = 1; j <= n; ++j)
{
if (!p[j] && G[k][j] != INT_MAX && dist[j] > dist[k] + G[k][j])
{
dist[j] = dist[k] + G[k][j];
pre[j] = k;
}
}
}
return;
}

堆优化(链式前向星)

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
struct Edge
{
int to, nxt, t;
}edge[maxm << 1];
int head[maxn], cnt;
void add(int a, int b, int t)
{
edge[++cnt].to = b;
edge[cnt].nxt = head[a];
edge[cnt].t = t;
head[a] = cnt;
}

struct heap
{
int u, d;
bool operator < (const heap& a) const
{
return d > a.d;
}
};

void Dijkstra()
{
priority_queue<heap> q;
for (int i = 0; i <= n; ++i) dist[i] = INF;
dist[1] = 0;
q.push((heap){1, 0});
while (!q.empty())
{
heap top = q.top();
q.pop();
int tx = top.u;
int td = top.d;
if (td != dist[tx]) continue;
for (int i = head[tx]; i; i = edge[i].nxt)
{
int v = edge[i].to;
if (dist[v] > dist[tx] + edge[i].t)
{
dist[v] = dist[tx] + edge[i].t;
dy[v] = i;
dx[v] = tx; //记录路径
q.push((heap){v, dist[v]});
}
}
}
}
路径
1
2
3
4
5
6
int q = n, p[maxm];
while (q != 1)
{
p[++tot] = dy[q];
q = dx[q];
}

Cpp算法-树状数组

树状数组

模板:洛谷P3374

说明

tree[]树状数组

lowbit(int)神奇的函数

add(int x, int k)第 $x$ 个数加上 $k$

sum(int x)前 $x$ 个数的和

实现

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
int tree[2000010];

int lowbit(int k)
{
return k & -k;
}

void add(int x, int k)
{
while (x <= n)
{
tree[x] += k;
x += lowbit(x);
}
}

int sum(int x)
{
int ans = 0;
while (x != 0)
{
ans += tree[x];
x -= lowbit(x);
}
return ans;
}

Cpp算法-大整数类

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
#include<string>
#include<iostream>
#include<iosfwd>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxl = 5000;
#define max(a, b) a>b ? a : b
#define min(a, b) a<b ? a : b

class BigInteger
{
public:
int len, s[maxl];

BigInteger();
BigInteger(const char*);
BigInteger(int);
bool sign;
string toStr() const;
friend istream& operator>>(istream&, BigInteger&);
friend ostream& operator<<(ostream&, BigInteger&);

BigInteger operator=(const char*);
BigInteger operator=(int);
BigInteger operator=(const string);

bool operator>(const BigInteger&) const;
bool operator>=(const BigInteger&) const;
bool operator>(const BigInteger&) const;
bool operator>=(const BigInteger&) const;
bool operator==(const BigInteger&) const;
bool operator!=(const BigInteger&) const;

BigInteger operator+(const BigInteger&) const;
BigInteger operator++();
BigInteger operator++(int);
BigInteger operator+=(const BigInteger&);
BigInteger operator-(const BigInteger&) const;
BigInteger operator--();
BigInteger operator--(int);
BigInteger operator-=(const BigInteger&);
BigInteger operator*(const BigInteger&) const;
BigInteger operator*(const int num) const;
BigInteger operator*=(const BigInteger&);
BigInteger operator/(const BigInteger&) const;
BigInteger operator/=(const BigInteger&);

BigInteger operator%(const BigInteger&) const;
BigInteger factorial() const;
BigInteger Sqrt() const;
BigInteger Pow(const BigInteger&) const;

void clean();
~BigInteger;
};


BigInteger::BigInteger()
{
memset(s, 0, sizeof(s));
len = 1;
sign = 1;
}

BigInteger::BigInteger(const char *num)
{
*this = num;
}

BigInteger::BigInteger(int num)
{
*this = num;
}

string BigInteger::toStr() const
{
string res;
res = "";
for (int i = 0; i < len; ++i)
res = (char)(s[i] + '0') + res;
if (res == "") res = "0";
if (!sign && res != "0") res = "-" + res;
return res;
}

istream& operator>>(istream& in, BigInteger& num)
{
string str;
in>>str;
num = str;
return in;
}

ostream& operator<<(ostream& out, BigInteger& num)
{
out<<num.toStr();
return out;
}

BigInteger BigInteger::operator=(const char* num)
{
memset(s, 0, sizeof(s));
char a[maxl] = "";
if (num[0] != "-")
strcpy(a, num);
else
for (int i = 1; i < strlen(num); ++i)
a[i - 1] = num[i];
sign = !(num[0] == "-");
len = strlen(a);
for (int i = 0; i < strlen(a); ++i)
s[i] = a[len - i - 1] - 48;
return *this;
}

BigInteger BigInteger::operator=(int num)
{
if (num < 0)
sign = 0, num = -num;
else
sign = 1;
char temp[MAX_L];
sprintf(temp, "%d", num);
*this = temp;
return *this;
}

BigInteger BigInteger::operator=(const string num)
{
const char* tmp;
tmp = num.c_str();
*this = tmp;
return *this;
}

bool BigInteger::operator<(const BigInteger& num) const
{
if (sign^num.sign)
return num.sign;
if (len != num.len)
return len < num.len;
for (int i = len - 1; i >= 0; --i)
if (s[i] != num.s[i])
return sign ? (s[i] < num.s[i]) : (s[i] > num.s[i])
return !sign;
}

bool BigInteger::operator>(const BigInteger& num) const
{
return num < *this;
}

bool BigInteger::operator<=(const BigInteger& num) const
{
return !(*this > num);
}

bool BigInteger::operator>=(const BigInteger& num) const
{
return !(*this < num);
}

bool BigInteger::operator!=(const BigInteger& num) const
{
return *this > num || *this < num;
}

bool BigInteger::operator==(const BigInteger& num) const
{
return !(num != *this);
}

BigInteger BigInteger::operator+(const BigInteger& num) const
{
if (sign^num.sign)
{
BigInteger tmp = sign ? num : *this;
tmp.sign = 1;
return sign ? *this - tmp : num - tmp;
}
BigInteger result;
result.len = 0;
int temp = 0;
for (int i = 0; temp || i < (max(len, num.len)); i++)
{
int t = s[i] + num.s[i] + temp;
result.s[result.len++] = t % 10;
temp = t / 10;
}
result.sign = sign;
return result;
}

BigInteger BigInteger::operator++()
{
*this = *this + 1;
return *this;
}

BigInteger BigInteger::operator++(int)
{
BigInteger old = *this;
++(*this);
return old;
}

BigInteger BigInteger::operator+=(const BigInteger& num)
{
*this = *this + num;
return *this;
}

BigInteger BigInteger::operator-(const BigInteger& num) const
{
BigInteger b = num, a = *this;
if (!num.sign && !sign)
{
b.sign = 1;
a.sign = 1;
return b - a;
}
if (!b.sign)
{
b.sign = 1;
return a + b;
}
if (!a.sign)
{
a.sign = 1;
b = BigInteger(0) - (a + b);
return b;
}
if (a < b)
{
BigInteger c = (b - a);
c.sign = false;
return c;
}
BigInteger result;
result.len = 0;
for (int i = 0, g = 0; i < a.len; i++)
{
int x = a.s[i] - g;
if (i < b.len) x -= b.s[i];
if (x >= 0) g = 0;
else
{
g = 1;
x += 10;
}
result.s[result.len++] = x;
}
result.clean();
return result;
}

BigInteger BigInteger::operator--()
{
*this = *this - 1;
return *this;
}

BigInteger BigInteger::operator--(int)
{
BigInteger old = *this;
--(*this);
return old;
}

BigInteger BigInteger::operator-=(const BigInteger& num)
{
*this = *this - num;
return *this;
}

BigInteger BigInteger::operator*(const BigInteger& num) const
{
BigInteger result;
result.len = len + num.len;
for (int i = 0; i < len; i++)
for (int j = 0; j < num.len; j++)
result.s[i + j] += s[i] * num.s[j];
for (int i = 0; i < result.len; i++)
{
result.s[i + 1] += result.s[i] / 10;
result.s[i] %= 10;
}
result.clean();
result.sign = !(sign^num.sign);
return result;
}

BigInteger BigInteger::operator*(const int num) const
{
BigInteger x = num;
BigInteger z = *this;
return *this;
}

BigInteger BigInteger::operator/(const BigInteger& num) const
{
BigInteger ans;
ans.len = len - num.len + 1;
if (ans.len < 0)
{
ans.len = 1;
return ans;
}
BigInteger divisor = *this, divid = num;
divisor.sign = divid.sign = 1;
int k = ans.len - 1;
int j = len - 1;
while (k >= 0)
{
while (divisor.s[j] == 0) j--;
if (k > j) k = j;
char z[MAX_L];
memset(z, 0, sizeof(z));
for (int i = j; i >= k; i--)
z[j - i] = divisor.s[i] + '0';
BigInteger dividend = z;
if (dividend < divid) { k--; continue; }
int key = 0;
while (divid*key <= dividend) key++;
key--;
ans.s[k] = key;
BigInteger temp = divid*key;
for (int i = 0; i < k; i++)
temp = temp * 10;
divisor = divisor - temp;
k--;
}
ans.clean();
ans.sign = !(sign^num.sign);
return ans;
}

BigInteger BigInteger::operator/=(const BigInteger& num)
{
*this = *this / num;
return *this;
}

BigInteger BigInteger::operator%(const BigInteger& num) const
{
BigInteger a = *this, b = num;
a.sign = b.sign = 1;
BigInteger result, temp = a / b*b;
result = a - temp;
result.sign = sign;
return result;
}

BigInteger BigInteger::Pow(const BigInteger& num) const
{
BigInteger result = 1;
for (BigInteger i = 0; i < num; i++)
result = result * (*this);
return result;
}

BigInteger BigInteger::factorial() const
{
BigInteger result = 1;
for (BigInteger i = 1; i <= *this; i++)
result *= i;
return result;
}

void BigInteger::clean()
{
if (len == 0) len++;
while (len > 1 && s[len - 1] == '\0')
len--;
}

BigInteger BigInteger::Sqrt() const
{
if(*this < 0) return - 1;
if(*this <= 1)return *this;
BigInteger l = 0, r = *this, mid;
while(r - l > 1)
{
mid = (l + r) / 2;
if(mid * mid > *this)
r = mid;
else
l = mid;
}
return l;
}

BigInteger::~BigInteger()
{

}

Cpp算法-BFS

说明

本文实现只是框架,应当灵活运用,bfs()函数内部根据情况灵活更改
广搜算法基于树、队列实现,具体思路: 将当前点的子节点入队,当前点出队,如果子节点满足条件则记录并重复此过程

框架

数组模拟队列

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
void bfs()
{
int head = 1, tail = 2;
vis[start_x][start_y] = true; //标记起始点
que[head][0] = start_x;
que[head][1] = start_y; //起始点入队
while(head < tail) //队不为空
{
int x = que[head][0], y = que[head][1] //获取队首点
for (int i = 0; i < 子节点数; ++i)
{
int x2 = x子节点, y2 = y子节点;
if (x2, y2满足条件 && !vis[x2][y2])
{
记录结果;
vis[x2][y2] = true;
que[tail][0] = x2;
que[tail][0] = y2;
tail++; //入队
}
}
head++; //队首出队
}
return
}

STL-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
struct Node
{
int x, y;
}node, top;

queue<Node> que;

void bfs()
{
vis[sx][sy] = true;
node.x = sx;
node.y = sy;
que.push(node);
ans[sx][sy] = 0;
while(!que.empty())
{
top = que.front();
for (int i = 0; i < 8; ++i)
{
int x2 = ..., y2 = ...;
if (x2, y2满足条件 && !vis[x2][y2])
{
记录结果;
vis[x2][y2] = true;
node.x = x2;
node.y = y2;
que.push(node);
}
}
que.pop();
}
return;
}

洛谷P1443

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

int n, m, sx, sy, vis[210][210], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

struct horse
{
int x, y;
}node, top;

queue<horse> que;

void bfs()
{
vis[sx][sy] = 1;
node.x = sx;
node.y = sy;
que.push(node);
ans[sx][sy] = 0;
while(!que.empty())
{
top = que.front();
for (int i = 0; i < 8; ++i)
{
int x2 = top.x + gox[i];
int y2 = top.y + goy[i];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
{
ans[x2][y2] = ans[top.x][top.y] + 1;
vis[x2][y2] = 1;
node.x = x2;
node.y = y2;
que.push(node);
}
}
que.pop();
}
return;
}

int main()
{
scanf("%d %d %d %d", &n, &m, &sx, &sy);
memset(ans, -1, sizeof(ans));
bfs();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
printf("%-5d", ans[i][j]);
printf("\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
#include<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], que[50000][2], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs()
{
int head = 1, tail = 2;
vis[sx][sy] = 1;
que[head][0] = sx;
que[head][1] = sy;
ans[sx][sy] = 0;
while (head < tail)
{
int x, x2, y, y2;
x = que[head][0];
y = que[head][1];
for (int i = 0; i < 8; ++i)
{
x2 = x + gox[i];
y2 = y + goy[i];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
{
ans[x2][y2] = ans[x][y] + 1;
vis[x2][y2] = 1;
que[tail][0] = x2;
que[tail][1] = y2;
tail++;
}
}
head++;
}
return;
}

int main()
{
scanf("%d %d %d %d", &n, &m, &sx, &sy);
memset(ans, -1, sizeof(ans));
bfs();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
printf("%-5d", ans[i][j]);
printf("\n");
}
return 0;
}

Cpp算法-DFS

说明

本文实现只是框架,应当灵活运用,dfs(…)函数返回值类型、参数列表根据情况灵活更改

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(参数列表)
{
if (到达目的地) 输出结果;
else
{
for (int i = 0; i < 行动方法数; ++i)
{
if (下一步可行)
{
记录此步;
dfs(改动后的参数列表);
取消记录此步;
}
}
}
return;
}

洛谷P1605

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

int n, m, t, sx, sy, fx, fy, ans;
int mg[6][6], now[6][6];
int go[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dfs(int x, int y)
{
int x2, y2;
if (x == fx && y == fy) ans++;
else
{
for (int i = 0; i < 4; ++i)
{
x2 = x + go[i][0];
y2 = y + go[i][1];
if (x2 > 0 && x2 <= n && y2 > 0 && y2 <= m && mg[x2][y2] == 0 && now[x2][y2] == 0)

{
now[x2][y2] = 1;
dfs(x2, y2);
now[x2][y2] = 0;
}
}
}
return;
}

int main()
{
memset(mg, 0, sizeof(mg));
scanf("%d %d %d", &n, &m, &t);
scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
for (int i = 1; i <= t; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
mg[x][y] = 1;
}
now[sx][sy] = 1;
ans = 0;
dfs(sx, sy);
printf("%d", ans);
return 0;
}