Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

板子们

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#define ll long long
#define ri register int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
ri v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const int N = 100010;
const int M = 100010;

template <typename T> inline T min(T x,T y) {return x<y?x:y;}
template <typename T> inline T max(T x,T y) {return x>y?x:y;}

存图

前向星存图,尽量不用结构体,绝对不用vector

1
2
3
4
5
6
7
8
9
int hd[N],edg[M],nxt[M],to[M],tot;

inline void add(int u,int v,int w) {
edg[++tot] = w;to[tot] = v;nxt[tot] = hd[u];hd[u] = tot;
}

inline void addedge(int u,int v,int w) {
add(u,v,w);add(v,u,w);
}

最短路

Dijkstra

带堆优化,时间复杂度$O(n\log n)$,在正权图以及SPFA被卡的情况适用

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
struct node {
int dis,num;
friend inline bool operator < (const node &a,const node &b) {
return a.dis > b.dis;
}
};

int dis[N],n,m,s;
bool vis[N],hasfuhuan;

void Dijkstra(int s) {
priority_queue <node> heap;
memset(dis,INF,sizeof(dis));
heap.push((node){dis[s] = 0,s});
while (!heap.empty()) {
node p = heap.top();heap.pop();
int x = p.num;
if (vis[x]) {
continue;
}
vis[x] = 1;
for (int i = hd[x];i;i = nxt[i]) {
int y = to[i],w = edg[i];
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
if (!vis[y]) {
heap.push((node){dis[y],y});
}
}
}
}
}

SPFA

最坏时间复杂度$O(nm)$,在证明不会被卡的时候用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SPFA(int s) {
queue <int> q;
vis[s] = 1;dis[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.front();q.pop();
vis[x] = 0;
for (int i = hd[x];i;i = nxt[i]) {
int y = to[i],w = edg[i];
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
if (!vis[y]) {
q.push(y);
vis[y] = 1;
}
}
}
}
}

Bellman-Ford

稳定时间复杂度$O(nm)$,判负环用 因为不会SPFA判负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Bellman_Ford(int s) {
memset(dis,INF,sizeof(dis));
dis[s] = 0;
int cnt = 0,flag = 1;
while (flag) {
for (int i = 0;i < m;++i) {
flag = 0;
int u = edges[i].u,v = edges[i].v,w = edges[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = 1;
}
if (++cnt > n) {
hasfuhuan = 1;
}
}
}
}

最小生成树

菜的要死只会Kruskal

Kruskal

并查集+排序 时间复杂度$O(m\log m)$,对于边数较少的图适用

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
//Union-Find Set
int f[N];

int find(int x) {
return f[x] == x ? f[x]:f[x] = find(f[x]);
}
//Kruskal
struct edge {
int u,v,w;
friend inline bool operator < (const edge &a,const edge &b) {
return a.w < b.w;
}
}edges[M];

int Kruskal() {
int tot = 0,ans = 0;
sort(edges+1,edges+1+n);
for (int i = 1;i <= m;++i) {
int u = edges[i].u,v = edges[i].v,w = edges[i].w;
if (find(u) != find(v)) {
ans += w;
++tot;
}
if (tot == n-1) {
break;
}
}
return ans;
}

拓扑排序

用来巧妙求解DAGdp等,利用BFS实现,同样可以用DFS实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cnt[N];
void toposort(int s) {
queue <int> q;
for (int i = 1;i <= n;++i) {
if (!cnt[i]) q.push(i);
}
while (!q.empty()) {
int u = q.front();
for (int i = hd[u];i;i = nxt[i]) {
int v = to[i];
if (--cnt[v] == 0) {
q.push(v);
}
}
}
}

树链剖分

树链剖分这个OIer很强

快速求解树上问题,具体应用请看树链剖分 学习笔记

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 dfn[N],top[N],siz[N],son[N],dep[N],fat[N];

void dfs1(int u,int f) {
son[u] = 0;
siz[u] = 1;
dep[u] = dep[f] + 1;
fat[u] = f;
for (int i = hd[u];i;i = nxt[i]) {
int v = to[i],w = edg[i];
if (v != f) {
dfs(v,u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) {
son[u] = v;
}
}
}
}

void dfs2(int u,int f) {
dfn[u] = ++cnt;
if (u == son[f]) {
top[u] = top[f];
}
else {
top[u] = u;
}
if (son[u]) {
dfs2(son[u],u);
}
for (int i = hd[u];i;i = nxt[i]) {
int v = to[i],w = edg[i];
if (v != f && v != son[u]) {
dfs2(v,u);
}
}
}