复习笔记_ SDOI2018前的板子总结

终于开始打板子了

乘法逆元(或$exgcd$)

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
#include <cstdio>
// ix % p = 1 -> ix + py = 1
int exgcd(int a, int b, int& x, int& y) // ax + by = 1
{
if (!b)
{
x = 1, y = 0;
return a;
}
int re = exgcd(b, a % b, y, x);
y -= a / b * x;
return re;
}
void solve(int i, int p)
{
int x, y, re = exgcd(i, p, x, y);
y = p / re;
while (x < 0)
x += y;
printf("%d\n", x);
}
int main()
{
int n, p;
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i++)
solve(i, p);
return 0;
}

负环(或$dfs-SPFA$)

注意回溯的时候将当前节点的vis置为false

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
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
using namespace std;
struct edg
{
int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, dis[MAXN];
bool ok, vis[MAXN];
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
void solve(int dq)
{
if (vis[dq])
{
ok = true;
return ;
}
vis[dq] = true;
for (int i = g[dq]; i; i = b[i].next)
if (dis[b[i].to] > dis[dq] + b[i].cost)
{
dis[b[i].to] = dis[dq] + b[i].cost;
solve(b[i].to);
if (ok)
return ;
}
vis[dq] = false;
}
int main()
{
int tim;
scanf("%d", &tim);
while (tim--)
{
memset(dis, 0, sizeof(dis));
memset(vis, false, sizeof(vis));
memset(g, 0, sizeof(g));
ok = false;
cntb = 0;
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i<= m; i++)
{
int srw, srx, sry;
scanf("%d%d%d", &srx, &sry, &srw);
adn(srx, sry, srw);
if (srw > 0)
adn(sry, srx, srw);
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
solve(i);
if (ok)
{
puts("YE5");
break;
}
}
if (!ok)
puts("N0");
}
return 0;
}

最大权路径(或tarjan缩点)

注意这里是一条路径…如果没有有向边是不能回来的…gg…

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define MAXN (1000000 + 5)
#define MAXM (5000000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
int from, to, next;
}b[MAXM << 1];
int g[MAXN], cntb, dfn[MAXN], low[MAXN], cntdfn, belong[MAXN], a[MAXN], f[MAXN];
stack<int> s;
bool ins[MAXN];
int find(int x)
{ return (x == belong[x] ? x : (belong[x] = find(belong[x]))); }
void uni(int x, int y)
{ belong[find(x)] = find(y); }
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
void tarjan(int dq)
{
dfn[dq] = low[dq] = ++cntdfn;
ins[dq] = true;
s.push(dq);
for (int i = g[dq]; i; i = b[i].next)
{
if (!dfn[b[i].to])
tarjan(b[i].to), low[dq] = min(low[dq], low[b[i].to]);
else if (ins[b[i].to])
low[dq] = min(low[dq], dfn[b[i].to]);
}
if (low[dq] == dfn[dq])
{
while (s.top() != dq)
{
ins[s.top()] = false; //
// belong[s.top()] = dq;
uni(s.top(), dq);
s.pop();
}
// belong[dq] = dq;
s.pop();
ins[dq] = false;
}
}
int solve(int dq)
{
if (f[dq] > -INF)
return f[dq];
f[dq] = 0;
for (int i = g[dq]; i; i = b[i].next)
if (find(b[i].from) != find(b[i].to)) // !=
f[dq] = max(f[dq], solve(find(b[i].to))); //belong[b[i].to]
return (f[dq] = f[dq] + a[dq]);
}
int main()
{
freopen("in.in", "r", stdin);
memset(ins, false, sizeof(ins));
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
belong[i] = i;
for (int i = 1; i <= m; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
adn(srx, sry);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i++)
if (i != find(i))
a[find(i)] += a[i];
for (int i = 1; i <= n; i++)
for (int j = g[i]; j; j = b[j].next)
if (find(b[j].from) != find(b[j].to)) // i -> j
adn(find(b[j].from), find(b[j].to)); // i -> j
memset(f, 0x8f, sizeof(f));
int ans = -INF;
for (int i = 1; i <= n; i++)
if (f[find(i)] <= - INF)
ans = max(ans, solve(find(i)));
printf("%d", ans);
return 0;
}

By 吃枣药丸的 Cansult