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