标签：std int dfn maxn 模板 now es

蒟蒻 Rainbow_Automaton 的模板

$\text{2023-10}$ 备战 $\text{csp-s}$

只是目前会的

~~然而目前啥也不会...~~

代码注意事项

不要使用using namespace std;
min 和 max 都可以直接 std::min std::max 吧
关同步 #define fastread std::ios_sync_with_stdio (false); cin.tie (0);
学习 jiangly using i64 = long long

图论

存图

~~这种东西真的需要记吗~~

写一个神秘的封装好的图

template<int maxn, int maxm>
struct Graph {
    struct Edge {
        int u, v;
        int pre;
    } es[maxm << 1];

    int last[maxn], cnt;

    Graph () { cnt = 0; memset (last, 0, sizeof (last)); }

    inline void addEdge (int u, int v) {
        es[++cnt] = Edge { u, v, last[u] };
        last[u] = cnt;
    }
};

然而我大部分时侯都不会用到封装好的图...

一般情况下只会直接写 Graph 里面的东西

最短路

Dijkstra

struct Node {
    int id;
    int dis;

    friend bool operator < (Node a, Node b) {
        return a.dis > b.dis; // 通过改符号的方向实现小根堆...
    }
};

std::priority_queue<Node> q;

int dis[maxn];
bool vis[maxn];
inline void dij (int S) {
    memset (vis, 0, sizeof (vis));
    memset (dis, 0x3f, sizeof (dis)); dis[S] = 0;
    q.push (Node { S, dis[S] });

    while (not q.empty()) {
        int now = q.top ().id; q.pop ();

        if (vis[now]) { continue; }
        vis[now] = true;

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (dis[t] > dis[now] + es[i].w) {
                dis[t] = dis[now] + es[i].w;
                q.push (Node { t, dis[t] });
            }
        }
    }
}

某个广为人所知的最短路算法

判负环

不判负环最好别用

~~才发现我单源最短路都是用 Dijkstra 过的~~

~~甚至找不到一个SPFA的板子~~

std::queue<int> q;
bool inq[maxn];
int times[maxn];

int dis[maxn];
inline bool spfa (int S) {
    q.push (S);
    memset (inq, 0, sizeof (inq)); inq[S] = true;
    memset (times, 0, sizeof (times)); times[S] = 0;
    for (int i = 1; i <= n + 1; i++) { if (i != S) { dis[i] = inf; } }

    while (not q.empty ()) {
        int now = q.front (); q.pop ();
        inq[now] = false;

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (dis[t] > dis[now] + es[i].w) {
                dis[t] = dis[now] + es[i].w;

                if (not inq[t]) {
                    inq[t] = true;
                    times[t] ++; if (times[t] > n + 1) { return false; } // 此处n + 1是因为多了一个超级源

                    q.push (t);
                }
            }
        }
    }

    return true;
}

差分约束

~~也许是唯一能用上SPFA的地方吧...~~

可以解出 $m$ 个形如 $X_u - X_v \leq Y$ 的不等式组成的不等式组的一个解

~~自然也可以判断是否有解~~

实质就是 $u - v \leq w \implies u \leq v + w \implies Edge_{v, u, w} $

$v$ 到 $u$ 连一条长度为 $w$ 的边

inline void diff_constraints () { // 差分约束
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;

        addEdge (v, u, w);
    }

    // 以n + 1作为超级源点
    for (int i = 1; i <= n; i++) { addEdge (n + 1, i, 0); }

    if (not spfa (n + 1)) { cout << "NO" << endl; }
    else {
        for (int i = 1; i <= n; i++) { cout << dis[i] << " "; }
    }
}

Floyd

int dis[maxn][maxn];

inline void init () {
    memset (dis, 0x3f, sizeof (dis));
    for (int i = 1; i <= n; i++) { dis[i][i] = 0; }
}

inline void floyd () {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = std::min (dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

注意先 init() 再加边

倍增Floyd

实际上是矩阵快速幂

把 $\text{Floyd}$ 原来的用 $dp[k][i][j]$ 表示前 $k$ 个点中 $i$ 到 $j$ 的最短路

改为用 $dp[s][i][j]$ 表示长度为 $s$ 的 $i$ 到 $j$ 的最短路

显然

$dp[s][i][j]$ 可以由 $ \min\limits_{k = 1}^{n} {dp[s - 1][i][k] + dp[1][k][j]}$ 转移过来

然后我们发现转移的过程和矩阵乘法特别像

用快速幂求出 $dp^k$ 就可以得到长为 $k$ 的路径条数

传递闭包

实际上就是 $01$ 矩阵上的 $\text{Floyd}$

只是求最短路改成求连通性了

std::bitset<maxn> a[maxn];

inline void floydClosure () {
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j]) { // i 能到 j
                a[i] |= a[j]; // 用j更新i
            }
        }
    }
}

上面的代码是用 bitset 写的, 与传统 $\text{Floyd}$ 略有不同

但是其基本思想是类似的

生成树

Kruskal

struct Edge {
    int u, v, w;

    friend bool operator < (Edge a, Edge b) {
        return a.w < b.w;
    }
};
std::vector<Edge> es;

inline int kruskal () {
    std::sort (es.begin (), es.end ());
    init ();

    int ans = 0;
    int tot = 0;

    for (auto e : es) {
        int u = find (e.u);
        int v = find (e.v);

        if (u == v) { continue; }

        fa[u] = v;
        ans += e.w;

        tot ++;
        if (tot == n - 1) { return ans; }
    }

    return -1;
}

其中 init() 就是并查集的 init()

并查集的写法看数据结构部分吧

Tarjan 系列

强连通分量

int low[maxn], dfn[maxn], dpos;
int stk[maxn], spos;
bool ins[maxn];

int belong[maxn], scc_cnt;
std::set<int> scc[maxn];

void tarjan (int now) {
    low[now] = dfn[now] = ++dpos;
    stk[++spos] = now;
    ins[now] = true;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t);
            low[now] = std::min (low[now], low[t]);
        } else if (ins[t]) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }

    if (low[now] == dfn[now]) {
        scc_cnt ++;
        do {
            belong[now] = scc_cnt;
            scc[scc_cnt].insert (now);
            ins[now] = false;

            now = stk[spos--];
        } while (low[now] != dfn[now]);
    }
}

2-SAT

用 $1$ 到 $n$ 表示 $a_i$ 取 $0$

用 $n + 1$ 到 $2 \times n$ 表示 $a_{i - n}$ 取 $1$

for (int i = 1; i <= 2 * n; i++) {
    if (not dfn[i]) { tarjan (i); }
}

if (not check ()) { std::cout << "IMPOSSIBLE" << "\n"; return 0; }

std::cout << "POSSIBLE" << "\n";
for (int i = 1; i <= n; i++) {
    if (scc[i + n] < scc[i]) { std::cout << 1 << " "; }
    else { std::cout << 0 << " "; }
}

割点

int low[maxn], dfn[maxn], dpos;
bool cut[maxn];

void tarjan (int now, int fa) {
    low[now] = dfn[now] = ++dpos;

    int sons = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, now);
            low[now] = std::min (low[now], low[t]);
            sons ++;
            if (low[t] >= dfn[now]) { cut[now] = true; }
        } else { // 此处可以考虑父亲
            low[now] = std::min (low[now], dfn[t]);
        }            
    }

    if (fa == 0 and sons < 2) { cut[now] = false; } 
}

点双连通分量

int low[maxn], dfn[maxn], dpos;
int stk[maxn], spos;

int belong[maxn], vdcc_cnt;
std::vector<int> vdcc[maxn];

void tarjan (int now, int fa) {
    low[now] = dfn[now] = ++dpos;
    stk[++spos] = now;

    int sons = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, now);
            low[now] = std::min (low[now], low[t]);

            sons ++;

            if (low[t] >= dfn[now]) {
                ++vdcc_cnt;

                int last = 0;
                while (last != t) {
                    int top = stk[spos--];
                    belong[top] = vdcc_cnt;
                    vdcc[vdcc_cnt].push_back (top);         
                    last = top;
                }
                vdcc[vdcc_cnt].push_back (now);
            }    
        } else {
            low[now] = std::min (low[now], dfn[t]);
        }
    }

    if (fa == 0 and sons == 0) { vdcc_cnt ++; vdcc[vdcc_cnt].push_back (now); }
}

桥

int low[maxn], dfn[maxn], dpos;
bool bridge[maxm << 1];

void tarjan (int now, int in_edge) {
    low[now] = dfn[now] = ++dpos;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, i);
            low[now] = std::min (low[now], low[t]);

            if (low[t] > dfn[now]) { bridge[i] = bridge[i ^ 1] = true; }

        } else if (i != (in_edge ^ 1)) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }
}

inline void init () { cnt = 1; }

因为涉及到快速找反向边, 一定要把 cnt 初始化为1!

边双连通分量

int low[maxn], dfn[maxn], dpos;
bool bridge[maxm << 1];

void tarjan (int now, int in_edge) {
    low[now] = dfn[now] = ++dpos;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, i);
            low[now] = std::min (low[now], low[t]);

            if (low[t] > dfn[now]) { bridge[i] = bridge[i ^ 1] = true; }

        } else if (i != (in_edge ^ 1)) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }
}   

int belong[maxn], edcc_cnt;
std::vector<int> edcc[maxn];

void dfs (int now) {
    belong[now] = edcc_cnt;
    edcc[edcc_cnt].push_back (now);
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (bridge[i]) { continue; }
        if (belong[t]) { continue; }

        dfs (t);
    }
}

inline void init () { cnt = 1; }

网络流

网络流的加边方式与普通图论问题的加边方式略有不同

struct Edge {
   int u, v;
   int pre;
   long long flow;
} es[maxm << 1];

int last[maxn], cur[maxn], cnt = 1;
int S, T;

inline void _addEdge (int u, int v, long long cap) {
   es[++cnt] = Edge { u, v, last[u], cap };
   last[u] = cnt;
}

inline void addEdge (int u, int v, long long cap) {
   _addEdge (u, v, cap);
   _addEdge (v, u, 0);
}

Dinic

int dep[maxn];

bool bfs () {
    std::queue<int> q; q.push (S);
    memset (dep, 0x3f, sizeof (dep)); dep[S] = 1;

    while (not q.empty ()) {
        int now = q.front (); q.pop ();

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;
            if (not es[i].flow) { continue; }
            if (dep[t] != 0x3f3f3f3f) { continue; }

            dep[t] = dep[now] + 1;
            q.push (t);
        }
    }

    return dep[T] != 0x3f3f3f3f;
}

long long dfs (int now, long long now_flow) {
    if (now == T or not now_flow) { return now_flow; }

    long long res = 0;
    for (int &i = cur[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not es[i].flow) { continue; }
        if (dep[t] != dep[now] + 1) { continue; }

        long long t_flow = dfs (t, std::min (now_flow, es[i].flow));

        if (t_flow) {
            es[i].flow -= t_flow;
            es[i ^ 1].flow += t_flow;
            now_flow -= t_flow;
            res += t_flow;

            if (not now_flow) { return res; }
        }
    }

    return res;
}

inline long long Dinic (int _s, int _t) {
    S = _s, T = _t;
    long long res = 0;
    while (bfs ()) {
        memcpy (cur, last, sizeof (last));
        res += dfs (S, 0x3f3f3f3f);
    }
    return res;
}

网络单纯形

咕咕咕

呜呜呜本来是会的

字符串

啥也不会

后缀自动机

struct SAM {
    struct Node {
        int ch[26];
        int fa;
        int len;
    } ns[maxn];

    int last, root, tot;

    // 附加信息
    i64 cnt[maxn];

    SAM () { last = root = tot = 1; memset (cnt, 0, sizeof (cnt)); }

    inline void add (int c) {
        int p = last;
        int np = last = ++tot;

        ns[np].len = ns[p].len + 1;
        cnt[np] = 1;

        for (; p and not ns[p].ch[c]; p = ns[p].fa) { ns[p].ch[c] = np; }

        if (not p) { ns[np].fa = root; }
        else {
            int q = ns[p].ch[c];

            if (ns[q].len == ns[p].len + 1) { ns[np].fa = q; }
            else {
                int nq = ++tot;
                ns[nq] = ns[q]; ns[nq].len = ns[p].len + 1;
                ns[q].fa = ns[np].fa = nq;

                for (; p and ns[p].ch[c] == q; p = ns[p].fa) { ns[p].ch[c] = nq; }
            }
        }
    }    

    inline void getParentTree (Graph& tr) {
        for (int i = 2; i <= tot; i++) { tr.addEdge (ns[i].fa, i); }
    }
};

数学

快速幂

i64 ksm (i64 a, i64 b, i64 mod) {
    i64 res = 1;
    i64 base = a;

    while (b) {
        if (b & 1) { (res *= base) %= mod; }
        (base *= base) %= mod;
        b >>= 1;
    }    

    return res;
}

欧拉函数

i64 phi (i64 n) {
    i64 ans = n;
    for (i64 p = 2; p * p <= n; p++) {
        if (n % p != 0) { continue; }

        ans = ans / p * (p - 1);
        while (n % p == 0) { n /= p; }
    }

    if (n > 1) { ans = ans / n * (n - 1); }

    return ans;
}

逆元

这里使用欧拉函数求逆元

~~不会写exgcd导致的~~

你说的对, 但是 $a ^ {\varphi(b)} = 1 \pmod b$

所以我们可以直接求逆元

i64 inv (i64 a, i64 b) {
    return Ksm::ksm (a, phi (b) - 1, b);
}

exgcd

i64 exgcd (i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    i64 d = exgcd (b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

于是, 上面的逆元也可以用exgcd求

因为

\[a \times inv_a \equiv 1 \pmod b \\ a \times inv_a + b \times y = 0 \]

所以我们很容易用exgcd求出 $inv_a$

inline i64 inv (i64 a, i64 b) {
    i64 x, y; exgcd (a, b, x, y);
    return (x + b) % b;       
}

线性筛

std::bitset<maxn> not_prime;
std::vector<int> primes;

inline void get_primes () {
    not_prime.reset ();
    not_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (not not_prime[i]) { primes.push_back (i); }

        for (auto p : primes) {
            if (i * p > n) { break; }
            not_prime[i * p] = true;
            if (i % p == 0) { break; }
        }
    }
}

线性筛莫比乌斯函数

顺便求出前缀和

inline void get_mu () {
    not_prime.reset ();
    int n = maxn - 5;

    mu[1] = 1;
    not_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (not not_prime[i]) { primes.push_back (i); mu[i] = -1; }

        for (auto p : primes) {
            if (i * p > n) { break; }
            not_prime[i * p] = true;
            mu[i * p] = -1 * mu[i];

            if (i % p == 0) { mu[i * p] = 0; break; }
        }
    }

    for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + mu[i]; }
}

中国剩余定理

只会大数翻倍法

~~orz钟神太强了%%%~~

inline bool merge (i64 &m1, i64 &a1, i64 m2, i64 a2) {
    if (m1 < m2) { std::swap (m1, m2); std::swap (a1, a2); }           

    while (a1 % m2 != a2) { a1 += m1; }

    m1 = lcm (m1, m2);

    return true;
}

扩展中国剩余定理

不用害怕, zhx的大数翻倍法本身就能合并两个同余方程

所以合并部分代码跟上面一样

数据结构

树状数组

template <int maxsiz>
struct BIT {
    int tr[maxsiz];

    inline int lowbit (int x) { return x & (-x); }

    inline void add (int pos, int val) { for (int i = pos; i <= n; i += lowbit(i)) { tr[i] += val; } }
    inline int _query (int pos) { int res = 0;for (int i = pos; i; i -= lowbit(i)) { res += tr[i]; } return res; }

    inline int query (int l, int r) { return _query (r) - _query (l - 1); }
};

上面只给出了单点加区间求和的版本

实际上, 树状数组还可以通过神秘的技术实现区间加单点查和 区间加区间求和

甚至可以通过跳 lowbit 实现 区间最值查询

然而实现十分复杂, 失去了树状数组本身简洁的优势

所以不如写线段树
标签：std,int,dfn,maxn,模板,now,es
From： https://www.cnblogs.com/RainbowAutomaton/p/18010693

蒟蒻的模板