板子们

qwq

头文件

#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

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被卡的情况适用

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)$，在证明不会被卡的时候用

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判负环

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)$，对于边数较少的图适用

//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实现

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很强

快速求解树上问题，具体应用请看[树链剖分 学习笔记](https://www.zzlblog.ga/2019/08/26/树链剖分 学习笔记/)

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);
		}
	}
}