算法模板
|
miyan
|
168
|
模板

1899 字
|
1.2 小时

0 初始化

0.1 初始化1

/*
     __  __   ___  __   __     _      _   _ 
    |  \/  | |_ _| \ \ / /    / \    | \ | |
    | |\/| |  | |   \ V /    / _ \   |  \| |
    | |  | |  | |    | |    / ___ \  | |\  |
    |_|  |_| |___|   |_|   /_/   \_\ |_| \_|

*/

#include <bits/stdc++.h>

#define endl '\n' 
#define all(a) a.begin(), a.end()

using namespace std;
using ull = unsigned long long;
using ll = long long;
using pii = pair<int, int>;

const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

template <typename T>
inline T read()
{
   T x = 0, f = 1;
   char ch = 0;
   for (; !isdigit(ch); ch = getchar())
       if (ch == '-')
          f = -1;
   for (; isdigit(ch); ch = getchar())
      x = (x << 3) + (x << 1) + (ch - '0');
   return x * f;
}

template <typename T>
inline void write(T x)
{
   if (x < 0)
      putchar('-'), x = -x;
   if (x > 9)
      write(x / 10);
   putchar(x % 10 + '0');
}

template <typename T>
inline void print(T x)
{
   write(x);
}

/* --------- 八嘎, 老子不是那么容易被打倒的, 我有的是毅力和时间 --------- */

void solve()
{

}

int main()
{
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

#ifdef LOCAL
    cerr << "Time used: " << clock() - c1 << " ms" << endl;
#endif

    return 0;
}

0.2 初始化2

/*
     __  __   ___  __   __     _      _   _ 
    |  \/  | |_ _| \ \ / /    / \    | \ | |
    | |\/| |  | |   \ V /    / _ \   |  \| |
    | |  | |  | |    | |    / ___ \  | |\  |
    |_|  |_| |___|   |_|   /_/   \_\ |_| \_|

*/

#include <bits/stdc++.h>

#define endl '\n' 
#define all(a) a.begin(), a.end()

using namespace std;
using ull = unsigned long long;
using ll = long long;
using pii = pair<int, int>;

const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

template <typename T>
inline T read()
{
   T x = 0, f = 1;
   char ch = 0;
   for (; !isdigit(ch); ch = getchar())
       if (ch == '-')
          f = -1;
   for (; isdigit(ch); ch = getchar())
      x = (x << 3) + (x << 1) + (ch - '0');
   return x * f;
}

template <typename T>
inline void write(T x)
{
   if (x < 0)
      putchar('-'), x = -x;
   if (x > 9)
      write(x / 10);
   putchar(x % 10 + '0');
}

template <typename T>
inline void print(T x)
{
   write(x);
}

/* --------- 八嘎, 老子不是那么容易被打倒的, 我有的是毅力和时间 --------- */

void solve()
{

}

int main()
{
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while(T--)
        solve();

#ifdef LOCAL
    cerr << "Time used: " << clock() - c1 << " ms" << endl;
#endif

    return 0;
}

1 基础算法

1.1 二分

1.1.1 整数

// 前驱
int l = 0, r = 1e9;
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid))
        l = mid;
    else
        r = mid - 1;
}

cout << l << endl;

// 后继
int l = 0, r = 1e9;
while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid))
        r = mid;
    else
        l = mid + 1;
}

cout << l << endl;

1.1.2 实数

double l = -1e20, r = 1e20;
while (r - l > 1e-8)
{
    double mid = (l + r) / 2;
    if (check(mid))
        r = mid;
    else
        l = mid;
}

1.2 前缀和

1.2.1 一维

// 前要：a原数组，n数组大小

// 前缀和数组
vi s(n + 10, 0);

// 前缀和计算
for (int i = 1; i <= n; ++i)
{
    s[i] = s[i - 1] + a[i];
}

// 前缀和输出
for (int i = 1; i <= n; ++i)
{
    cout << s[i] << ' ';
}

1.2.2 二维

// 前要：a原数组，n行m列

// 前缀和数组
vvi s(n + 10, vi(m + 10, 0));

// 前缀和计算
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
}

// 输出左上为(x1,y1)右下为(x2,y2)区间的和
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;

1.3 差分

1.3.1 一维

// 前要：a原数组，n数组大小

// 差分数组
vi b(n + 10, 0);

// 差分计算
for (int i = 1; i <= n; ++i)
    b[i] = a[i] - a[i - 1];

// 在[l,r]区间上加上一个v
int l, r, v;
cin >> l >> r >> v;
b[l] += v, b[r + 1] -= v;

// 前缀和运算恢复原数组
for (int i = 1; i <= n; ++i)
    b[i] += b[i - 1];

1.3.2 二维

// 前要：a原数组，n行m列

//b差分数组
vvi b(n + 10, vi(m + 10, 0));

// 插入函数
auto insert = [&](int x1, int y1, int x2, int y2, int v)
{
    b[x1][y1] += v;
    b[x2 + 1][y1] -= v;
    b[x1][y2 + 1] -= v;
    b[x2 + 1][y2 + 1] += v;
};

// 构造差分数组
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        insert(i, j, i, j, a[i][j]);

// 在区间上累加值v
int x1, y1, x2, y2, v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
insert(x1, y1, x2, y2, v);

// 前缀和运算恢复原数组
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

1.4 位运算

1.4.1 lowbit

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

1.5 最大子数组和

1.5.1 kadane

// n 个元素

int n;
cin >> n;

vector<ll> f(n + 10, 0);
ll ans = MIN; // 全局最大子数组和
for (int i = 1; i <= n; ++i)
{
    ll x;
    cin >> x;
    f[i] = max(x, f[i - 1] + x);
    ans = max(ans, f[i]);
}

cout << ans << endl;

1.5.2 贪心

// n 个元素

int n;
cin >> n;

ll ans = MIN, cnt = 0; // // ans 全局最大子数组和，cnt 局部最大子数组和
for (int i = 0; i < n; ++i)
{
    int x;
    cin >> x;
    if (cnt < 0)
        cnt = 0;
    cnt += x;
    ans = max(ans, cnt);
}

cout << ans << endl;

1.6 归并排序求逆序对

int tmp[N]; // 临时数组

ll merge_sort(int q[], int l, int r) // 对 q 数组求逆序对
{
    if (l >= r)
        return 0;

    int mid = l + r >> 1;

    ll ans = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
        {
            ans += mid - i + 1;
            tmp[k++] = q[j++];
        }
    }

    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    for (int i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];

    return ans;
}

2 数据结构

2.1 并查集

// 0-based

struct DSU
{
    vector<int> f, siz;

    DSU() {}
    DSU(int n) { init(n); }

    void init(int n)
    {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        while (x != f[x])
        {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
        {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) { return siz[find(x)]; }
};

2.2 哈希表

2.2.1 数字哈希 – 开放寻址法

// 前要：N数组最大大小

// 极限值
const int INF = 0x7f7f7f7f;

// 哈希数组
vi h(N + 10, INF);

// find函数
auto find = [&](int x) -> int
{
    int t = (x % N + N) % N;
    while (h[t] != INF && h[t] != x)
    {
        if (++t == N)
            t = 0;
    }
    return t;
};

// 操作1：将数字映射到哈希表中
int x;
cin >> x;
h[find(x)] = x;

// 操作2：判断哈希表中有没有值
int x;
cin >> x;
if (h[find(x)] == INF)
    cout << "NO" << endl;
else
    cout << "YES" << endl;

2.3 树状数组

// 维护区间和
// n 个节点

int n;
int a[N];
ll tr[N];

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

// 单点修改
void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += v;
}

// 区间查询
ll query(int x)
{
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += tr[i];
    return ans;
}

2.4 线段树

2.4.1 单点修改 区间查询

2.4.1.1 区间最小值
// 1 - based
// 传递线段树大小和初始值数组
// eq: SegmentTreeMin<int> st(n, v);

template <typename T>
struct SegmentTreeMin
{
    struct Node
    {
        int l, r;
        T minn;
    };

    // 线段树大小
    int N;
    vector<Node> tr;
    vector<T> v;

    SegmentTreeMin(int _N, const vector<T> &_v)
    {
        N = _N;
        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = _v[i];
        tr.resize(4 * N);
        build(1, 1, N);
    }

    // 左右子区间
    #define LC (u << 1)
    #define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].minn = min(tr[LC].minn, tr[RC].minn);
    }

    inline void build(int u, int l, int r)
    {
        if (l == r)
        {
            tr[u] = {l, r, v[l]};
            return;
        }

        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        pushup(u);
    }

    inline T query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u].minn;

        int mid = tr[u].l + tr[u].r >> 1;
        T ans = std::numeric_limits<T>::max(); // 当前类型能表示的最大值
        if (l <= mid)
            ans = min(ans, query(LC, l, r));
        if (r > mid)
            ans = min(ans, query(RC, l, r));
        return ans;
    }

    inline void update(int u, int x, T val)
    {
        if (tr[u].l == x && tr[u].r == x)
        {
            tr[u].minn = val;
            return;
        }

        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            update(LC, x, val);
        else
            update(RC, x, val);
        pushup(u);
    }

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

    inline void update(int x, T val) { update(1, x, val); }
};
2.4.1.2 区间最大子数组和
// 1 - based
// 传递线段树大小和节点初始值
// eq: SegmentTreeMaxSum<ll> st(n, -1);

template <typename T>
struct SegmentTreeMaxSum
{
    struct Node
    {
        int l, r;
        // 区间总和 区间前缀最大和 区间后缀最大和 区间最大子段和
        T sum, pre, suf, val;
    };

    int N;
    vector<Node> tr;
    vector<T> v;

    // init_value：节点初始值
    SegmentTreeMaxSum(int _N, T init_value)
    {
        N = _N;

        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = init_value;

        tr.resize(4 * N);
        build(1, 1, N);
    }

    #define LC (u << 1)
    #define RC (u << 1 | 1)

    inline Node merge(const Node &a, const Node &b)
    {
        Node ans;
        ans.l = a.l;
        ans.r = b.r;
        ans.sum = a.sum + b.sum;
        ans.pre = max(a.pre, a.sum + b.pre);
        ans.suf = max(b.suf, b.sum + a.suf);
        ans.val = max({a.val, b.val, a.suf + b.pre});
        return ans;
    }

    inline void build(int u, int l, int r)
    {
        if (l == r)
        {
            tr[u] = {l, r, v[l], v[l], v[l], v[l]};
            return;
        }
        int mid = l + r >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        tr[u] = merge(tr[LC], tr[RC]);
    }

    inline void update(int u, int x, T val)
    {
        if (tr[u].l == x && tr[u].r == x)
        {
            tr[u] = {x, x, val, val, val, val};
            return;
        }

        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            update(LC, x, val);
        else
            update(RC, x, val);
        tr[u] = merge(tr[LC], tr[RC]);
    }

    inline Node query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u];

        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid)
            return query(LC, l, r);
        if (l > mid)
            return query(RC, l, r);
        return merge(query(LC, l, r), query(RC, l, r));
    }

    inline void update(int x, T val) { update(1, x, val); }

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

2.4.2 区间修改 区间查询

2.4.2.1 区间和 + 区间累加
// 1 - based
// 传递线段树大小和初始值数组
// eq: SegmentTreeLazySumRangeAccumulate<ll> st(n, v);

template <typename T>
struct SegmentTreeLazySumRangeAccumulate
{
    struct Node
    {
        int l, r;
        T sum;
        T add;
    };

    // 线段树大小
    int N;
    vector<Node> tr;
    vector<T> v;

    SegmentTreeLazySumRangeAccumulate(int _N, const vector<T> &_v)
    {
        N = _N;
        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = _v[i];
        tr.resize(4 * N);
        build(1, 1, N);
    }

// 左右子区间
#define LC (u << 1)
#define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].sum = tr[LC].sum + tr[RC].sum;
    }

    inline void pushdown(int u)
    {
        if (tr[u].add)
        {
            tr[LC].sum += tr[u].add * (tr[LC].r - tr[LC].l + 1);
            tr[RC].sum += tr[u].add * (tr[RC].r - tr[RC].l + 1);
            tr[LC].add += tr[u].add;
            tr[RC].add += tr[u].add;
            tr[u].add = 0;
        }
    }

    inline void build(int u, int l, int r)
    {
        if (l == r)
        {
            tr[u] = {l, r, v[l], 0};
            return;
        }
        tr[u] = {l, r, 0, 0};
        int mid = (l + r) >> 1;
        build(LC, l, mid), build(RC, mid + 1, r);
        pushup(u);
    }

    inline T query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u].sum;

        pushdown(u);

        int mid = (tr[u].l + tr[u].r) >> 1;
        T sum = 0;
        if (l <= mid)
            sum = query(LC, l, r);
        if (r > mid)
            sum += query(RC, l, r);
        return sum;
    }

    inline void update(int u, int l, int r, T v)
    {
        if (tr[u].l >= l && tr[u].r <= r)
        {
            tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
            tr[u].add += v;
            return;
        }

        int mid = (tr[u].l + tr[u].r) >> 1;
        pushdown(u);
        if (l <= mid)
            update(LC, l, r, v);
        if (r > mid)
            update(RC, l, r, v);
        pushup(u);
    }

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

    inline void update(int l, int r, T val) { update(1, l, r, val); }
};
2.4.2.2 区间和 + 区间赋值
// 1 - based
// 传递线段树大小和初始值数组
// eq: SegmentTreeLazySumAssign<ll> st(n, v);

template <typename T>
struct SegmentTreeLazySumAssign
{
    struct Node
    {
        int l, r;
        T sum;
        T assign; // 懒标记，-1 表示没有赋值操作
    };

    int N;
    vector<Node> tr;
    vector<T> v;

    SegmentTreeLazySumAssign(int _N, const vector<T> &_v)
    {
        N = _N;
        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = _v[i];
        tr.resize(4 * N);
        build(1, 1, N);
    }

#define LC (u << 1)
#define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].sum = (tr[LC].sum + tr[RC].sum) % MOD;
    }

    inline void apply_assign(int u, T val)
    {
        tr[u].sum = (tr[u].r - tr[u].l + 1) * val % MOD;
        tr[u].assign = val;
    }

    inline void pushdown(int u)
    {
        if (tr[u].assign != -1)
        {
            apply_assign(LC, tr[u].assign);
            apply_assign(RC, tr[u].assign);
            tr[u].assign = -1;
        }
    }

    inline void build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, -1};
        if (l == r)
        {
            tr[u].sum = v[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        pushup(u);
    }

    inline T query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return tr[u].sum;

        pushdown(u);

        T sum = 0;
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid)
            sum = (sum + query(LC, l, r)) % MOD;
        if (r > mid)
            sum = (sum + query(RC, l, r)) % MOD;
        return sum % MOD;
    }

    inline void update(int u, int l, int r, T val)
    {
        if (tr[u].l >= l && tr[u].r <= r)
        {
            apply_assign(u, val);
            return;
        }

        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid)
            update(LC, l, r, val);
        if (r > mid)
            update(RC, l, r, val);
        pushup(u);
    }

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

    inline void update(int l, int r, T val) { update(1, l, r, val); }
};

3 数论

3.1 gcd

3.1.1 欧几里得算法

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

3.1.2 位运算加速

略快于内置__gcd函数。

ll gcd(ll a, ll b)
{
    #define tz __builtin_ctzll
    if (!a || !b)
        return a | b;
    int t = tz(a | b);
    a >>= tz(a);
    while (b)
    {
        b >>= tz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    }
    return a << t;
    #undef tz
}

3.2 lcm

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

3.3 质数筛

3.3.1 判质数

3.3.1.1 朴素

$O(\sqrt{n})$。

auto check = [](int x) -> bool
{
    if (x < 2)
        return 0;
    for (int i = 2; i <= x / i; ++i)
    {
        if (!(x % i))
            return 0;
    }

    return 1;
};
3.3.1.2 预分类讨论加速

$\mathcal{O}\left(\frac{\sqrt{N}}{3}\right)$。

auto check = [](int x) -> bool
{
    if (x < 2)
        return 0;
    if (x == 2 || x == 3)
        return 1;
    if (x % 6 != 1 && x % 6 != 5)
        return 0;
    for (int i = 5, j = x / i; i <= j; i += 6)
    {
        if (x % i == 0 || x % (i + 2) == 0)
        {
            return 0;
        }
    }
    return 1;
};

3.3.2 埃式筛

vector<int> prime;

void get_prime(int n)
{
    vector<bool> st(n + 10, 0);
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            prime.push_back(i);
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

3.3.3 欧拉筛（线性筛）

vector<int> prime;

void get_prime(int n)
{
    vector<bool> st(n + 10, 0);
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            prime.push_back(i);
        for (int j = 0; prime[j] <= n / i; ++j)
        {
            st[prime[j] * i] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}

3.4 快速幂

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

3.5 乘法逆元

3.5.1 模数为质数

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

ll inv(ll q, ll mod)
{
    return qmi(q, mod - 2, mod);
}

3.6 组合数

// 需要预处理出 1 - n 的阶乘和其逆元

auto C = [&](ll n, ll m) -> ll
{
    if (n < 0 || m < 0 || n < m)
        return 0;
    if (n == m)
        return 1;

    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
};

4 图论

1.图的存储

（1）邻接矩阵（稠密图）

// 前要：n个点的图

// 存图
vvi g(n + 10, vi(n + 10, 0));

auto add = [&](int u, int v, int w) -> void
{
    g[u][v] = w;           // 有向图
    g[u][v] = g[v][u] = w; // 无向图
};

// u 到 v 有一条边权为 w 的边
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);

（2）邻接表（稀疏图）

动态数组
有边权
// 前要：n个点的图

// 存图
vector<pii> g[n + 10];

auto add = [&](int u, int v, int w) -> void
{
    // 有向图
    g[u].push_back({v, w});
    g[v].push_back({u, w});

    // 无向图
    g[u].push_back({v, w});
};

// u 到 v 有一条边权为 w 的边
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
无边权
// 前要：n个点的图

// 存图
vi g[n + 10];

auto add = [&](int u, int v) -> void
{
    // 有向图
    g[u].pb(v);
    g[v].pb(u);

    // 无向图
    g[u].pb(v);
};

// u 到 v 有一条边
int u, v;
cin >> u >> v;
add(u, v);
链式前向星
有边权
// 前要：n个点的图

// 存图
int h[N], e[N], ne[N], w[N], idx;

// 初始化
me(h, -1);

auto add = [&](int a, int b, int c) -> void
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
};

// a 到 b 有一条边权为 c 的边
int a, b, c;
cin >> a >> b >> c;
// 有向图
add(a, b, c);
add(b, a, c);
// 无向图
add(a, b, c);
无边权
// 前要：n个点的图

// 存图
int h[N], e[N], ne[N], idx;

// 初始化
me(h, -1);

auto add = [&](int a, int b) -> void
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
};

// a 到 b 有一条边
int a, b;
cin >> a >> b;
// 有向图
add(a, b);
add(b, a);
// 无向图
add(a, b);

2.dijkstra（堆优化）

// n 个点，m 条边，起点 1
int n, m;
cin >> n >> m;
vector<pii> g[n + 10];

auto add = [&](int u, int v, int w) -> void
{
    g[u].push_back({v, w});
};

while (m--)
{
    int u, v, w;
    cin >> u >> v >> w;
    add(u, v, w);
}

vi d(n + 10, 0x7f7f7f7f);
vb st(n + 10, 0);
auto dijkstra = [&]() -> void
{
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, 1});
    d[1] = 0;

    while (q.size())
    {
        auto [distance, u] = q.top();
        q.pop();

        if (st[u])
            continue;
        st[u] = 1;

        for (auto [v, w] : g[u])
        {
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }
};

3.spfa

// n 个点，m 条边，起点 1

int n, m;
cin >> n >> m;
vector<pii> g[n + 10];

for (int i = 0; i < m; ++i)
{
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w});
}

vi dist(n + 10, MAX);
vi st(n + 10, 0);

auto spfa = [&]() -> void
{
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    st[1] = 1;

    while (q.size())
    {
        auto u = q.front();
        q.pop();

        st[u] = 0;

        for (auto [v, w] : g[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (!st[v])
                {
                    q.push(v);
                    st[v] = 1;
                }
            }
        }
    }
};

4.负环

// 前要：n个点 m条无向边
// 判断从1点开始可以到达的边有没有负环

int n, m;
cin >> n >> m;
vector<pii> g[n + 10];

for (int i = 0; i < m; ++i)
{
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);   //无向图
    g[v].emplace_back(u, w);
}

vi cnt(n + 10, 0);  // 统计每个点松弛次数
vi dist(n + 10, MAX);
vi st(n + 10, 0);
auto spfa = [&]() -> bool
{
    // 如果是判断整张图有没有负环需要将全部点加入到队列中
    queue<int> q;
    q.push(1);
    ++cnt[1];
    st[1] = 1;
    dist[1] = 0;

    while (q.size())
    {
        auto u = q.front();
        q.pop();

        st[u] = 0;

        for (auto [v, w] : g[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (!st[v])
                {
                    st[v] = 1;
                    q.push(v);

                    if (++cnt[v] >= n)
                        return 1;
                }
            }
        }
    }

    return 0;
};

5.floyd

// n 个点

int n;
cin >> n;
vii g(n + 10, vi(n + 10, 0));  //邻接矩阵
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        cin >> g[i][j];

auto floyd = [&]() -> void
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
};

6.树的直径

/*
    树，n 个节点，n - 1 条边
    1 - based
*/

int n;
cin >> n;
vector<vector<int>> g(n + 10);
for (int i = 0; i < n - 1; ++i)
{
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}

vector<int> dist(n + 10, 0);
auto dfs = [&](auto &&self, int u, int f) -> void
{
    for (auto v : g[u])
    {
        if (v != f)
        {
            dist[v] = dist[u] + 1;
            self(self, v, u);
        }
    }
};

int u = 1;
dfs(dfs, u, 0);

u = max_element(dist.begin() + 1, dist.begin() + n + 1) - dist.begin();

// fill(dist.begin(), dist.end(), 0);
ranges::fill(dist, 0);
dfs(dfs, u, 0);

u = max_element(dist.begin() + 1, dist.begin() + n + 1) - dist.begin();

// 直径
cout << dist[u] << endl;

7.拓扑排序

// 前要：n个点，m条边，有向图
// 注：如果要使字典序最小就将队列换为优先队列即可。

int n, m;
cin >> n >> m;
vi g[n + 10];
vi du(n + 10, 0);
while (m--)
{
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    ++du[v];
}

vi ans;  // topo序
auto toposort = [&]() -> void
{
    queue<int> q;

    for (int i = 1; i <= n; ++i)
    {
        if (!du[i])
            q.push(i);
    }

    while (q.size())
    {
        auto u = q.front();
        q.pop();

        ans.push_back(u);

        for (auto v : g[u])
        {
            if (--du[v] == 0)
                q.push(v);
        }
    }
};

toposort();

for (auto x : ans)
    cout << x << ' ';
cout << endl;

8.Kruskal

// 前要：n个点，m条边

int n, m;
cin >> n >> m;
vector<array<int, 3>> g;

for (int i = 0; i < m; ++i)
{
    int u, v, w;
    cin >> u >> v >> w;
    g.push_back({u, v, w});
}

sort(all(g), [](auto &a, auto &b)
     { return a[2] < b[2]; });

vi f(n + 10, 0);
for (int i = 1; i <= n; ++i)
    f[i] = i;

function<int(int)> find = [&](int x) -> int
{
    if (x != f[x])
        f[x] = find(f[x]);
    return f[x];
};

ll ans = 0;  // 最小生成树权重之和
ll cnt = 0;  // 选择的边数
auto kruskal = [&]() -> void
{
    for (auto [u, v, w] : g)
    {
        u = find(u), v = find(v);

        if (u != v)
        {
            f[u] = v;
            ans += w;
            ++cnt;
        }
    }
};

9.最短路计数

// 前要：n个点，m条边

int n, m;
cin >> n >> m;
vi g[n + 10];
for (int i = 0; i < m; ++i)
{
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
}

vi dist(n + 10, MAX);
vi st(n + 10, 0);
vi ans(n + 10, 0); // 统计1点到其他点最短路径个数
ans[1] = 1;

auto dijkstra = [&]() -> void
{
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, 1});
    dist[1] = 0;

    while (q.size())
    {
        auto [d, u] = q.top();
        q.pop();

        if (st[u])
            continue;
        st[u] = 1;

        for (auto v : g[u])
        {
            int distance = dist[u] + 1;
            if (dist[v] > distance)
            {
                dist[v] = distance;
                ans[v] = ans[u] % MOD;
                q.push({dist[v], v});
            }
            else if (dist[v] == distance)
                ans[v] = (ans[v] + ans[u]) % MOD;
        }
    }
};

10.树中各子树大小

// 前要：n个点，n - 1条边，使用vector存储

vector<int> size(n + 10, 1);
function<void(int, int)> dfs = [&](int u, int f) -> void
{
    for (auto v : g[u])
    {
        if (v == f)
            continue;

        dfs(v, u);

        size[u] += size[v];
    }
};

5 技巧

5.1 排序去重

a.erase(unique(a.begin(), a.end()), a.end());

5.2 十进制转二进制

bitset<32> bit(x);
cout << bit << endl;
模板

评论

  1. chy
    3 月前
    2025-7-19 19:20:16

    好腻害

  4. duck_lite
    3 月前
    2025-7-19 19:28:10

    太强了

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇