造数据相关知识

· · 科技·工程

有错误请指出，立马修改！

如果有想添加的函数或函数伪随机请私信。

Python

CYaRon（头文件）

CYaRon：测试数据生成利器

C++

注意事项

Testlib（头文件）

Testlib——最强出题辅助工具库

批量生成数据

推荐使用命令行参数 + bat/sh 的方法。

例如：

gen.cpp:

#include "testlib.h"

using namespace std;

int n, m, k;
vector<int> p;

int main(int argc, char* argv[]) {
  registerGen(argc, argv, 1);

  int i;

  n = atoi(argv[1]);
  m = atoi(argv[2]);
  k = rnd.next(1, n);

  for (i = 1; i <= n; ++i) p.push_back(i);

  shuffle(p.begin(), p.end());
  // 使用 rnd.next() 进行 shuffle

  printf("%d %d %d\n", n, m, k);
  for (i = 0; i < n; ++i) {
    printf("%d%c", p[i], " \n"[i == n - 1]);
    // 把字符串当作数组用，中间空格，末尾换行，是一个造数据时常用的技巧
  }

  return 0;
}

gen_scripts.bat:

gen 10 10 > 1.in
gen 1 1 > 2.in
gen 100 200 > 3.in
gen 2000 1000 > 4.in
gen 100000 100000 > 5.in

这样做的好处是，对于不同的数据只需要写一个 generator，并且可以方便地修改某个测试点的参数。

----OI Wiki 出题

造数据（模板）

data1.cpp:（批量生成数据）

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
namespace rad {
    mt19937_64 R(time(0));
    inline int Rand(int l,int r) {
        uniform_int_distribution<int> distribution(l,r);
        return distribution(R);
    }
} using namespace rad;
int main() {
    string in,out;
    for(int i = 1;i <= 3;i ++) { // 序号 
        in.clear();
        int j = i;
        while(j) {
            char m = j % 10 + '0';
            in = m + in;
            j /= 10;
        }
        out = in;
        in += ".in";
        out += ".out";
        string A = "name"; // 文件名 
        string B = "name";
        A = A + in,B = B + out;
        in = A,out = B;
        freopen(in.data(),"w",stdout);
        system("data.exe"); // 数据生成器 
        fclose(stdout);
        string Str="std.exe < "+ in +" > "+ out; // 你的 std 
        system(Str.data());
    }
}

data.cpp:（造数据模板）

#include <bits/stdc++.h>
#include <stdexcept>
#define int long long
using namespace std;

/*
* __int128 读写支持
* 注意：部分编译器可能不支持__int128类型
*/

/**
 * @brief 从标准输入读取一个__int128类型的整数
 * @details 该函数从标准输入中读取字符序列，解析为__int128类型的整数，支持负数。
 *          它会跳过非数字字符，直到遇到数字或负号，并正确处理多位数字。
 * @return 返回读取到的__int128类型整数
 * @warning 如果输入超出__int128范围，可能导致未定义行为
 */
__int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

/**
 * @brief 将__int128类型的整数输出到标准输出
 * @details 该函数将__int128类型的整数按十进制形式输出到标准输出，支持负数。
 *          它通过递归方式处理多位数字，逐位输出。
 * @param x 要输出的__int128类型整数
 * @return 无返回值
 */
void write(__int128 x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

/*
* 128位整数随机生成器
* 功能：生成指定范围的128位整数
* 原理：组合两个64位随机数生成完整128位空间
*/

/**
 * @brief 128位整数均匀分布随机数生成器类
 * @details 该类用于生成指定范围内的__int128类型随机整数，利用两个64位随机数拼接生成128位随机数。
 *          它基于C++的随机数引擎mt19937_64实现。
 */
class uniform_int128_distribution {
private:
    using u128 = unsigned __int128;
    __int128 _min, _max;  // 范围边界
    mt19937_64 _gen;      // 64位随机引擎

public:
    /**
     * @brief 构造函数，初始化随机数生成器的范围
     * @details 验证输入范围的有效性，并初始化随机数引擎。
     * @param a 随机数范围下限
     * @param b 随机数范围上限
     * @throws invalid_argument 如果范围无效（a > b）
     */
    uniform_int128_distribution(__int128 a, __int128 b) : _gen(mt19937_64(random_device{}())) {
        if (a > b) throw invalid_argument("Invalid range");
        _min = a;
        _max = b;
    }

    /**
     * @brief 生成一个指定范围内的随机__int128整数
     * @details 通过组合两个64位随机数生成128位随机数，并将其映射到指定范围。
     * @return 返回一个在[min, max]范围内的__int128类型随机整数
     */
    __int128 operator()() {
        u128 range = static_cast<u128>(_max - _min) + 1;
        u128 rand_val = (static_cast<u128>(_gen()) << 64) | _gen();
        return _min + static_cast<__int128>(rand_val % range);
    }
};

/*
* 随机数生成命名空间
* 包含各种数据结构的随机生成方法
*/
namespace rad {
    mt19937_64 R(random_device{}()); // 全局随机引擎

    /*
    * 基础随机数生成函数
    * 模板参数：整数类型
    * 参数：l-范围下限，r-范围上限
    */

    /**
     * @brief 生成指定范围内的随机整数
     * @details 该函数生成类型为T的随机整数，范围为[l, r]，基于C++的均匀分布随机数生成器。
     * @tparam T 整数类型（如int, long long等）
     * @param l 随机数范围下限
     * @param r 随机数范围上限
     * @return 返回一个在[l, r]范围内的随机整数
     * @throws static_assert 如果T不是整数类型
     */
    template<typename T>
    T Rand(T l, T r) {
        static_assert(is_integral<T>::value, "T must be integral type");
        uniform_int_distribution<T> dis(l, r);
        return dis(R);
    }

    /**
     * @brief 生成指定范围内的随机浮点数（long double特化版本）
     * @details 该函数生成范围为[l, r]的随机浮点数，基于C++的均匀分布随机数生成器。
     * @param l 随机数范围下限
     * @param r 随机数范围上限
     * @return 返回一个在[l, r]范围内的随机浮点数
     */
    template<>
    long double Rand<long double>(long double l, long double r) {
        uniform_real_distribution<long double> dis(l, r);
        return dis(R);
    }

    /*
    * 生成128位整数
    * 参数：l-下限，r-上限
    * 注意：输出需使用write函数
    */

    /**
     * @brief 生成指定范围内的随机__int128整数
     * @details 该函数利用uniform_int128_distribution类生成范围为[l, r]的随机__int128整数。
     * @param l 随机数范围下限
     * @param r 随机数范围上限
     * @return 返回一个在[l, r]范围内的随机__int128整数
     */
    __int128 Rand128(__int128 l, __int128 r) {
        static uniform_int128_distribution gen(l, r);
        return gen();
    }

    /*
    * 容器操作函数
    * Shuffle：随机打乱容器元素
    * RandChoice：从容器中随机选取元素
    */

    /**
     * @brief 随机打乱向量中的元素
     * @details 该函数使用C++的shuffle算法，基于全局随机引擎R，随机打乱向量v中的元素。
     * @tparam T 向量元素类型
     * @param v 待打乱的向量（引用传递，会修改原向量）
     * @return 无返回值
     */
    template<typename T>
    void Shuffle(vector<T>& v) {
        shuffle(v.begin(), v.end(), R);
    }

    /**
     * @brief 从向量中随机选择一个元素
     * @details 该函数从非空向量v中随机选择一个元素并返回其引用。
     * @tparam T 向量元素类型
     * @param v 待选择的向量（const引用，不会修改原向量）
     * @return 返回随机选择的元素的const引用
     * @throws runtime_error 如果向量为空
     */
    template<typename T>
    const T& RandChoice(const vector<T>& v) {
        if (v.empty()) throw runtime_error("Cannot choose from empty vector");
        return v[Rand<size_t>(0, v.size() - 1)];
    }

    /*
    * 树生成器类
    * 支持生成多种树结构
    */
    class Tree {
    public:
        enum Type {
            RANDOM, // 随机树（默认）
            CHAIN,  // 链状结构
            STAR,   // 星型结构
            BINARY  // 近似二叉树结构
        };

        // 边结构体：u起点，v终点，w边权
        struct Edge {
            int u, v, w;
            Edge(int _u, int _v, int _w = 1) : u(_u), v(_v), w(_w) {}
        };

        /**
         * @brief 生成指定类型的树结构
         * @details 该函数根据指定的树类型生成一棵包含n个节点的树，支持随机树、链状树、星型树和近似二叉树。
         *          边的权值在[min_w, max_w]范围内随机生成。
         * @param n 节点数
         * @param type 树类型，默认为随机树（RANDOM）
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @return 返回一个包含所有边的向量，每条边由Edge结构体表示
         * @throws invalid_argument 如果节点数n <= 0
         */
        static vector<Edge> generate(int n, Type type = RANDOM, int min_w = 1, int max_w = 1e9) {
            if (n <= 0) throw invalid_argument("Node count must be positive");
            vector<Edge> edges;
            switch (type) {
                case CHAIN:  // 链状生成
                for (int i = 2; i <= n; ++i) edges.emplace_back(i - 1, i, Rand(min_w, max_w));
                break;
                case STAR:   // 星型生成
                for (int i = 2; i <= n; ++i) edges.emplace_back(1, i, Rand(min_w, max_w));
                break;
                case BINARY: { // 二叉树生成
                    queue<int> q;
                    q.push(1);
                    int cnt = 1;
                    while (cnt < n) {
                        int u = q.front(); q.pop();
                        int left = ++cnt;
                        edges.emplace_back(u, left, Rand(min_w, max_w));
                        q.push(left);
                        if (cnt >= n) break;
                        int right = ++cnt;
                        edges.emplace_back(u, right, Rand(min_w, max_w));
                        q.push(right);
                    }
                    break;
                }
                default:  // 随机生成（Prufer序列方式）
                for (int i = 2; i <= n; ++i) edges.emplace_back(Rand(1LL, i - 1), i, Rand(min_w, max_w));
            }
            shuffle_edges(edges, n);  // 打乱节点编号和边顺序
            return edges;
        }

        // 定义输出方式的枚举
        enum OutputFormat {
            EDGE_LIST,      // 边列表（默认）
            ADJ_LIST,       // 邻接表
            PARENT_ARRAY    // 父节点数组
        };

        /**
         * @brief 封装的树生成和输出函数
         * @details 该函数生成指定类型的树，并根据指定的输出格式打印树结构。
         *          支持带文字描述和无文字描述的输出，通过verbose参数控制。
         * @param n 节点数
         * @param type 树类型
         * @param format 输出格式
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @param verbose 是否输出带文字描述的版本，默认为true
         * @throws invalid_argument 如果节点数n <= 0或输出格式无效
         */
        static void generate_and_print_tree(int n, Type type, OutputFormat format, int min_w = 1, int max_w = 1e9, bool verbose = true) {
            // 生成树
            auto edges = generate(n, type, min_w, max_w);

            // 根据选择的格式输出树
            switch (format) {
                case EDGE_LIST: { // 边列表格式
                    if (verbose) cout << "边列表格式 (u - v 边权: w):\n";
                    for (const auto& e : edges) cout << e.u << " " << e.v << " " << e.w << "\n";
                    break;
                }
                case ADJ_LIST: { // 邻接表格式
                    // 构建邻接表
                    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表，pair<邻居, 边权>
                    for (const auto& e : edges) {
                        adj[e.u].emplace_back(e.v, e.w);
                        adj[e.v].emplace_back(e.u, e.w); // 无向图，双向添加
                    }
                    if (verbose) {
                        cout << "邻接表格式:\n";
                        for (int i = 1; i <= n; ++i) if (!adj[i].empty()) {
                            cout << "节点 " << i << " 的邻居: ";
                            for (const auto& [v, w] : adj[i]) cout << "(" << v << ", 边权: " << w << ") ";
                            cout << "\n";
                        }
                    } else {
                        // 无文字描述，仅输出数据
                        // 每行格式：节点编号 邻居数量 邻居1 边权1 邻居2 边权2 ...
                        for (int i = 1; i <= n; ++i) if (!adj[i].empty()) {
                            cout << i << " " << adj[i].size();
                            for (const auto& [v, w] : adj[i]) cout << " " << v << " " << w;
                            cout << "\n";
                        }
                    }
                    break;
                }
                case PARENT_ARRAY: { // 父节点数组格式
                    // 构建父节点数组
                    vector<int> parent(n + 1, -1); // 父节点数组，-1 表示根节点
                    vector<int> weights(n + 1, 0); // 记录到父节点的边权
                    // 使用 BFS 确定父节点关系
                    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表，用于 BFS
                    for (const auto& e : edges) {
                        adj[e.u].emplace_back(e.v, e.w);
                        adj[e.v].emplace_back(e.u, e.w); // 无向图，双向添加
                    }
                    queue<int> q;
                    vector<bool> visited(n + 1, false);
                    int root = 1; // 固定选择节点1作为根
                    q.push(root);
                    visited[root] = true;
                    while (!q.empty()) {
                        int u = q.front(); q.pop();
                        for (const auto& [v, w] : adj[u]) if (!visited[v]) {
                            visited[v] = true;
                            parent[v] = u;
                            weights[v] = w;
                            q.push(v);
                        }
                    }
                    if (verbose) {
                        cout << "父节点数组格式 (parent[i] 表示节点 i 的父节点):\n根节点: " << root << "\n节点 | 父节点 | 到父节点的边权\n";
                        for (int i = 1; i <= n; ++i) if (i != root && parent[i] != -1) {
                            cout << i << "    | " << parent[i] << "      | " << weights[i] << "\n";
                        }
                    } else {
                        // 无文字描述，仅输出数据
                        // 格式：根节点编号\n节点编号 父节点编号 边权（仅非根节点）
                        cout << root << "\n";
                        for (int i = 1; i <= n; ++i) if (i != root && parent[i] != -1) {
                            cout << i << " " << parent[i] << " " << weights[i] << "\n";
                        }
                    }
                    break;
                }
                default: throw invalid_argument("Unknown output format");
            }
        }

    private:
        /**
         * @brief 边随机化处理：打乱节点编号和边顺序
         * @details 该函数打乱树的节点编号和边顺序，确保节点编号在 [1, n] 内，增加随机性。
         * @param edges 待处理的边向量（引用传递，会修改原向量）
         * @param n 节点数
         * @return 无返回值
         */
        static void shuffle_edges(vector<Edge>& edges, int n) {
            if (edges.empty()) return;
            // 生成 1 到 n 的随机排列
            vector<int> perm(n);
            iota(perm.begin(), perm.end(), 1);
            shuffle(perm.begin(), perm.end(), R);
            // 映射节点编号
            for (auto& e : edges) {
                if (Rand(0LL, 1LL)) swap(e.u, e.v); // 随机方向
                e.u = perm[e.u - 1]; // 映射到随机节点编号
                e.v = perm[e.v - 1];
            }
            // 随机化边顺序
            rad::Shuffle(edges);
        }
    };

    /*
    * 图生成器类
    * 支持生成多种图结构
    */
    class Graph {
    public:
        enum OutputFormat {
            EDGE_LIST,       // 默认边列表(每行u v w)
            TRIPLE_LINES,    // 三行分别输出u、v、w数组
            COLUMNAR,        // 列式存储：所有u一行，所有v一行，所有w一行
            INTERLEAVED_LINE,// 所有边数据挤在一行
            ADJACENCY_LIST   // 邻接表格式
        };

        struct Edge {
            int u, v, w;
        };

        static void print_array(const vector<int>& arr, const string& prefix, bool verbose) {
            if (verbose) cout << prefix;
            for (int x : arr) cout << x << " ";
            cout << "\n";
        }

        /**
         * @brief 生成完全随机图
         * @details 该函数生成包含n个节点和m条边的随机图，边的权值在[min_w, max_w]范围内随机生成
         *          支持有向图和无向图，通过directed参数控制
         * @param n 节点数
         * @param m 边数
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @param directed 是否生成有向图，默认为false
         * @return 返回一个包含所有边的向量
         * @throws invalid_argument 如果参数不合法
         */
        static vector<Edge> random(int n, int m, int min_w = 1, int max_w = 1e9, bool directed = false) {
            if (n <= 0) throw invalid_argument("Node count must be positive");
            int max_edges = directed ? n * (n - 1) : n * (n - 1) / 2;
            if (m < 0 || m > max_edges) throw invalid_argument("Invalid edge count");
            vector<Edge> edges;
            set<pair<int, int>> edge_set;
            while (edges.size() < m) {
                int u = Rand(1LL, n), v = Rand(1LL, n);
                if (u == v) continue;
                if (!directed && u > v) swap(u, v);
                if (edge_set.count({u, v})) continue;
                edges.push_back({u, v, Rand(min_w, max_w)});
                edge_set.insert({u, v});
            }
            return edges;
        }

        /**
         * @brief 生成并打印随机图（多格式版）
         * @param output_format 输出格式枚举值
         * @param sorted 是否按边权排序后输出
         */
        static void generate_and_print_random_graph(int n, int m, OutputFormat output_format = EDGE_LIST, bool sorted = false, int min_w = 1, int max_w = 1e9, bool directed = false, bool verbose = true) {
            auto edges = random(n, m, min_w, max_w, directed);
            if (sorted) sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
            switch (output_format) {
            case EDGE_LIST:
                if (verbose) cout << "边列表格式：\n";
                for (const auto& e : edges) cout << e.u << " " << e.v << " " << e.w << "\n";
                break;
            case TRIPLE_LINES:
                if (verbose) cout << "三行格式：\n";
                for (const auto& e : edges) cout << e.u << " "; cout << "\n";
                for (const auto& e : edges) cout << e.v << " "; cout << "\n";
                for (const auto& e : edges) cout << e.w << " "; cout << "\n";
                break;
                case COLUMNAR: {
                    if (verbose) cout << "列式存储：\n";
                    vector<int> us, vs, ws;
                    for (const auto& e : edges) { us.push_back(e.u); vs.push_back(e.v); ws.push_back(e.w); }
                    print_array(us, "U: ", verbose); print_array(vs, "V: ", verbose); print_array(ws, "W: ", verbose);
                    break;
                }
            case INTERLEAVED_LINE:
                if (verbose) cout << "单行交错格式：\n";
                for (const auto& e : edges) cout << e.u << " " << e.v << " " << e.w << " ";
                cout << "\n";
                break;
                case ADJACENCY_LIST: {
                    if (verbose) cout << "邻接表格式：\n";
                    map<int, vector<pair<int, int>>> adj;
                    for (const auto& e : edges) {
                        adj[e.u].emplace_back(e.v, e.w);
                        if (!directed) adj[e.v].emplace_back(e.u, e.w);
                    }
                    for (const auto& [u, neighbors] : adj) {
                        cout << u << ": ";
                        for (const auto& [v, w] : neighbors) cout << "(" << v << "," << w << ") ";
                        cout << "\n";
                    }
                    break;
                }
            }
        }

        /**
         * @brief 生成连通图
         * @details 该函数生成一个包含n个节点和m条边的连通图，边的权值在[min_w, max_w]范围内随机生成。
         *          支持有向图和无向图，通过directed参数控制。
         * @param n 节点数
         * @param m 边数（必须 >= n-1 以保证连通性）
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @param directed 是否生成有向图，默认为false
         * @return 返回一个包含所有边的向量，每条边由Edge结构体表示
         * @throws invalid_argument 如果节点数n <= 0 或边数m < n-1
         */
        static vector<Edge> connected(int n, int m, int min_w = 1, int max_w = 1e9, bool directed = false) {
            if (n <= 0) throw invalid_argument("Node count must be positive");
            if (m < n - 1) throw invalid_argument("Edge count must be at least n-1 for connectivity");
            auto tree = Tree::generate(n);
            vector<Edge> edges;
            set<pair<int, int>> edge_set;
            for (auto& e : tree) {
                edges.push_back({e.u, e.v, Rand(min_w, max_w)});
                if (directed) edge_set.insert({e.u, e.v});
                else edge_set.insert({min(e.u, e.v), max(e.u, e.v)});
            }
            while ((int)edges.size() < m) {
                int u = Rand(1LL, n), v = Rand(1LL, n);
                if (u == v) continue;
                if (!directed && u > v) swap(u, v);
                if (edge_set.count({u, v})) continue;
                edges.push_back({u, v, Rand(min_w, max_w)});
                edge_set.insert({u, v});
            }
            return edges;
        }

        /**
         * @brief 生成连通图并打印
         * @details 该函数生成连通图，并根据verbose参数选择带文字描述或无文字描述的输出。
         * @param n 节点数
         * @param m 边数
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @param directed 是否生成有向图，默认为false
         * @param verbose 是否输出带文字描述的版本，默认为true
         * @throws invalid_argument 如果节点数n <= 0 或边数m < n-1
         */
        static void generate_and_print_graph(int n, int m, int min_w = 1, int max_w = 1e9, bool directed = false, bool verbose = true) {
            auto edges = connected(n, m, min_w, max_w, directed);
            if (verbose) {
                cout << "连通图边列表格式 (" << (directed ? "u -> v" : "u - v") << " 边权: w):\n";
                for (const auto& e : edges) cout << e.u << (directed ? " -> " : " - ") << e.v << " 边权: " << e.w << "\n";
            } else {
                for (const auto& e : edges) cout << e.u << " " << e.v << " " << e.w << "\n";
            }
        }

        /**
         * @brief 生成有向无环图（DAG）
         * @details 该函数生成一个包含n个节点和m条边的有向无环图，边的权值在[min_w, max_w]范围内随机生成。
         *          通过拓扑排序生成边，确保无环。
         * @param n 节点数
         * @param m 边数
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @return 返回一个包含所有边的向量，每条边由Edge结构体表示
         * @throws invalid_argument 如果节点数n <= 0 或边数m < 0
         */
        static vector<Edge> DAG(int n, int m, int min_w = 1, int max_w = 1e9) {
            if (n <= 0) throw invalid_argument("Node count must be positive");
            if (m < 0) throw invalid_argument("Edge count must be non-negative");
            vector<int> ord(n);
            iota(ord.begin(), ord.end(), 1);
            Shuffle(ord);
            set<pair<int, int>> edges;
            while (edges.size() < m) {
                int u = Rand(0LL, n - 2);
                int v = Rand(u + 1, n - 1);
                edges.insert({ord[u], ord[v]});
            }
            vector<Edge> res;
            for (auto& [u, v] : edges) res.push_back({u, v, Rand(min_w, max_w)});
            return res;
        }

        /**
         * @brief 生成有向无环图（DAG）并打印
         * @details 该函数生成有向无环图，并根据verbose参数选择带文字描述或无文字描述的输出。
         * @param n 节点数
         * @param m 边数
         * @param min_w 最小边权，默认为1
         * @param max_w 最大边权，默认为1e9
         * @param verbose 是否输出带文字描述的版本，默认为true
         * @throws invalid_argument 如果节点数n <= 0 或边数m < 0
         */
        static void generate_and_print_dag(int n, int m, int min_w = 1, int max_w = 1e9, bool verbose = true) {
            auto edges = DAG(n, m, min_w, max_w);
            if (verbose) {
                cout << "有向无环图边列表格式 (u -> v 边权: w):\n";
                for (const auto& e : edges) cout << e.u << " -> " << e.v << " 边权: " << e.w << "\n";
            } else {
                for (const auto& e : edges) cout << e.u << " " << e.v << " " << e.w << "\n";
            }
        }

        /**
         * @brief 生成用于挑战SPFA算法的菊花链图 (Daisy Chain Graph)
         * @details 该函数生成一种特殊的有向图，旨在使SPFA算法达到其O(V*E)的最坏时间复杂度。
         *          其结构为：一个源点(1)，一个中心节点(n)，以及k条连接它们的“链”。
         *          1. 源点1连接到第一条链的开头。
         *          2. 每条链由若干节点串联而成，边权较小。
         *          3. 每条链的末端连接到中心节点n，边权也较小。
         *          4. 中心节点n再连接回除第一条链外的所有链的开头，形成“菊花瓣”间的通路。
         *          这种结构会导致SPFA在更新中心节点n的距离后，需要沿着“通路”反复更新所有链上节点的距离，
         *          从而导致节点被大量重复入队，性能急剧下降。
         *          通常，以节点1为源点运行SPFA会触发最坏情况。
         * @param n 节点总数，节点编号为 1 到 n。
         * @param k “菊花”的“花瓣”数量，即链的数量。推荐 k 约为 sqrt(n)。
         * @param min_w 最小边权，默认为0。
         * @param max_w 最大边权，默认为100。建议使用较小的非负权值。
         * @return 返回一个包含所有边的向量，专门用于测试SPFA。
         * @throws invalid_argument 如果参数不合法 (e.g., n, k 太小)。
         */
        static vector<Edge> hack_spfa(int n, int k, int min_w = 0, int max_w = 100) {
            if (n < 3 || k < 2 || n <= k) throw invalid_argument("For Hack-SPFA graph: n must be >= 3, k >= 2, n > k.");
            if ((n - 2) / k < 1) throw invalid_argument("Each chain must have at least one node.");
            vector<Edge> edges;
            int center_node = n, current_node_idx = 1;
            int base_chain_len = (n - 2) / k, remainder = (n - 2) % k;
            vector<int> chain_starts;
            for (int i = 0; i < k; ++i) {
                int chain_start = current_node_idx;
                chain_starts.push_back(chain_start);
                int current_chain_len = base_chain_len + (i < remainder ? 1 : 0);
                int u = chain_start;
                for (int j = 0; j < current_chain_len - 1; ++j) {
                    int v = u + 1;
                    edges.push_back({u, v, (int)Rand(min_w, max_w)});
                    u = v;
                }
                edges.push_back({u, center_node, (int)Rand(min_w, max_w)});
                current_node_idx = u + 1;
            }
            for (size_t i = 1; i < chain_starts.size(); ++i)
                edges.push_back({center_node, chain_starts[i], (int)Rand(min_w, max_w)});
            return edges;
        }

        /**
         * @brief 生成并打印用于挑战SPFA算法的图
         * @details 调用 hack_spfa 函数生成图，并根据verbose参数选择带文字描述或无文字描述的输出。
         * @param n 节点总数
         * @param k 链的数量
         * @param min_w 最小边权
         * @param max_w 最大边权
         * @param verbose 是否输出带文字描述的版本，默认为true
         */
        static void generate_and_print_hack_spfa(int n, int k, int min_w = 0, int max_w = 100, bool verbose = true) {
            auto edges = hack_spfa(n, k, min_w, max_w);
            int m = edges.size();
            if (verbose) {
                cout << "SPFA-Hack (菊花链图) 边列表格式 (u -> v 边权: w):\n总节点数: " << n << ", 总边数: " << m << "\n建议以节点 1 作为源点进行最短路计算。\n";
                for (const auto& e : edges) cout << e.u << " -> " << e.v << " 边权: " << e.w << "\n";
            } else {
                cout << n << " " << m << "\n";
                for (const auto& e : edges) cout << e.u << " " << e.v << " " << e.w << "\n";
            }
        }
    };

    /*
    * 数组生成器类
    * 生成特殊结构的数组
    */
    class Array {
    public:
        /**
         * @brief 生成随机排列
         * @details 该函数生成一个包含1到n的随机排列。
         * @param n 元素个数
         * @return 返回一个包含随机排列的向量
         * @throws invalid_argument 如果元素个数n <= 0
         */
        static vector<int> permutation(int n, int l, int r) {
            if (n <= 0) throw invalid_argument("Size must be positive");
            vector<int> res(n);
            for (int i = 0; i < n; ++i) res[i] = Rand(l, r);
            Shuffle(res);
            return res;
        }

        /**
         * @brief 生成随机排列并打印
         * @details 该函数生成一个包含1到n的随机排列，并根据verbose参数选择带文字描述或无文字描述的输出。
         * @param n 元素个数
         * @param verbose 是否输出带文字描述的版本，默认为true
         * @throws invalid_argument 如果元素个数n <= 0
         */
        static void generate_and_print_permutation(int n, int l, int r, bool verbose = true) {
            auto perm = permutation(n, l, r);
            if (verbose) cout << "随机排列: ";
            for (int x : perm) cout << x << " ";
            cout << "\n";
        }

        /**
         * @brief 生成唯一元素数组（无重复）
         * @details 该函数生成一个包含n个唯一元素的数组，元素值在[min_v, max_v]范围内随机生成。
         * @tparam T 元素类型
         * @param n 元素个数
         * @param min_v 最小值
         * @param max_v 最大值
         * @return 返回一个包含唯一元素的向量
         * @throws invalid_argument 如果元素个数n <= 0 或范围不足以生成n个唯一元素
         */
        template<typename T>
        static vector<T> unique(int n, T min_v, T max_v) {
            if (n <= 0) throw invalid_argument("Size must be positive");
            if (max_v - min_v + 1 < n) throw invalid_argument("Range too small for unique elements");
            set<T> s;
            while (s.size() < n) s.insert(Rand(min_v, max_v));
            vector<T> res(s.begin(), s.end());
            Shuffle(res);
            return res;
        }

        /**
         * @brief 生成唯一元素数组并打印
         * @details 该函数生成一个包含n个唯一元素的数组，并根据verbose参数选择带文字描述或无文字描述的输出。
         * @tparam T 元素类型
         * @param n 元素个数
         * @param min_v 最小值
         * @param max_v 最大值
         * @param verbose 是否输出带文字描述的版本，默认为true
         * @throws invalid_argument 如果元素个数n <= 0 或范围不足以生成n个唯一元素
         */
        template<typename T>
        static void generate_and_print_unique(int n, T min_v, T max_v, bool verbose = true) {
            auto arr = unique(n, min_v, max_v);
            if (verbose) cout << "唯一元素数组: ";
            for (const auto& x : arr) cout << x << " ";
            cout << "\n";
        }

        /**
         * @brief 生成山峰数组
         * @details 该函数生成一个包含n个元素的山峰数组，数组先递增后递减或先递减后递增，
         *          元素值在[min_val, max_val]范围内随机生成。如果峰值位置选择不当，会尝试不同的位置。
         * @param n 元素个数
         * @param min_val 最小值限制，默认为0
         * @param max_val 最大值限制，默认为1e9
         * @param is_peak_max 是否生成峰值最大的数组（true为先增后减，false为先减后增），默认为true
         * @param strict 是否严格单调，默认为true
         * @return 返回一个包含山峰数组的向量
         * @throws invalid_argument 如果元素个数n <= 0 或n < 2 或 min_val >= max_val 或无法生成满足条件的序列
         */
        static vector<int> mountain(int n, int min_val = 0, int max_val = 1e9, bool is_peak_max = true, bool strict = true) {
            if (n <= 0 || n < 2 || min_val >= max_val) throw invalid_argument("Invalid parameters for mountain array");
            if (strict && (long long)max_val - min_val < n - 1) throw invalid_argument("Range too small for strict monotonic sequence");
            vector<int> res(n);
            int peak = Rand(1LL, n - 2); // 确保峰值不在两端
            if (is_peak_max) {
                res[peak] = max_val;
                for (int i = peak - 1; i >= 0; --i) res[i] = strict ? res[i + 1] - Rand(1LL, (max_val - min_val) / (peak + 1)) : Rand(min_val, res[i + 1]);
                for (int i = peak + 1; i < n; ++i) res[i] = strict ? res[i - 1] - Rand(1LL, (max_val - min_val) / (n - peak)) : Rand(min_val, res[i - 1]);
            } else {
                res[peak] = min_val;
                for (int i = peak - 1; i >= 0; --i) res[i] = strict ? res[i + 1] + Rand(1LL, (max_val - min_val) / (peak + 1)) : Rand(res[i + 1], max_val);
                for (int i = peak + 1; i < n; ++i) res[i] = strict ? res[i - 1] + Rand(1LL, (max_val - min_val) / (n - peak)) : Rand(res[i - 1], max_val);
            }
            return res;
        }

        /**
         * @brief 生成山峰数组并打印
         * @details 该函数生成一个山峰数组，并根据verbose参数选择带文字描述或无文字描述的输出。
         * @param n 元素个数
         * @param min_val 最小值限制，默认为0
         * @param max_val 最大值限制，默认为1e9
         * @param is_peak_max 是否生成峰值最大的数组，默认为true
         * @param strict 是否严格单调，默认为true
         * @param verbose 是否输出带文字描述的版本，默认为true
         * @throws invalid_argument 如果元素个数n <= 0 或n < 2 或 min_val >= max_val 或无法生成满足条件的序列
         */
        static void generate_and_print_mountain(int n, int min_val = 0, int max_val = 1e9, bool is_peak_max = true, bool strict = true, bool verbose = true) {
            auto arr = mountain(n, min_val, max_val, is_peak_max, strict);
            if (verbose) cout << (is_peak_max ? "山峰" : "山谷") << "数组: ";
            for (int x : arr) cout << x << " ";
            cout << "\n";
        }
    };

    /**
     * @class StringGenerator
     * @brief 字符串生成器类
     * @details 提供生成各类字符串及字符串集合的功能，包括随机字符串，
     *          以及专门用于导致标准库哈希表（如 std::unordered_map）哈希碰撞的特殊字符串集。
     */
    class StringGenerator {
    public:
        /**
         * @brief 生成一个指定长度的随机字符串。
         * @param len 要生成的字符串的长度。
         * @param charset 用于生成字符串的字符集，默认为大小写字母。
         * @return 一个随机生成的字符串。
         */
        static string random(int len, const string& charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") {
            if (len < 0 || charset.empty()) throw invalid_argument("Invalid parameters for random string");
            string result;
            result.reserve(len);
            for (int i = 0; i < len; ++i) result += charset[Rand(0LL, (int)(charset.length() - 1))];
            return result;
        }

        /**
         * @brief 生成一个随机字符串列表。
         * @param count 要生成的字符串数量。
         * @param min_len 每个字符串的最小长度。
         * @param max_len 每个字符串的最大长度。
         * @param charset 使用的字符集。
         * @return 一个包含随机字符串的向量。
         */
        static vector<string> random_list(int count, int min_len, int max_len, const string& charset = "abcdefghijklmnopqrstuvwxyz") {
            if (count < 0 || min_len < 0 || max_len < min_len) throw invalid_argument("Invalid parameters for random list");
            vector<string> result;
            result.reserve(count);
            for (int i = 0; i < count; ++i) result.push_back(random(Rand(min_len, max_len), charset));
            return result;
        }

        /**
         * @brief 生成一组旨在导致哈希碰撞的字符串
         * @details 通过生成短字符串并按哈希值低位分组，构造一组长字符串，增加在 std::unordered_map 中落入同一桶的概率。
         * @param count 要生成的字符串数量
         * @param base_len 每个字符串的大致长度
         * @param charset 用于生成字符串的字符集
         * @return 返回一个可能导致哈希碰撞的字符串向量
         * @throws invalid_argument 如果参数无效
         */
        static vector<string> hack_hash_table(int count, int base_len = 10, const string& charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789") {
            if (count < 0 || base_len < 0 || charset.empty()) throw invalid_argument("无效的参数");
            if (count == 0) return {};

            // 生成短字符串（长度为3）并按哈希值低位分组
            const int short_len = 3;
            const size_t mask = (1ULL << 20) - 1; // 使用低20位进行分组，假设桶数为2的幂
            map<size_t, vector<string>> hash_groups;

            // 生成所有可能的长度为3的字符串（限制样本量以提高效率）
            size_t max_samples = min((size_t)1000000, (size_t)pow(charset.size(), short_len));
            set<string> used_strings;
            vector<char> chars(charset.begin(), charset.end());

            for (size_t i = 0; i < max_samples; ++i) {
                string s;
                for (int j = 0; j < short_len; ++j) {
                    s += chars[Rand(0LL, (int)charset.size() - 1)];
                }
                if (used_strings.insert(s).second) {
                    size_t hash = std::hash<string>{}(s) & mask;
                    hash_groups[hash].push_back(s);
                }
            }

            // 找到包含最多字符串的组
            size_t max_size = 0;
            size_t selected_hash = 0;
            for (const auto& [hash, group] : hash_groups) {
                if (group.size() > max_size) {
                    max_size = group.size();
                    selected_hash = hash;
                }
            }

            // 如果没有找到至少有两个字符串的组，回退到随机字符串
            if (max_size < 2) {
                vector<string> result;
                set<string> result_set;
                while (result.size() < count) {
                    string s = random(Rand(base_len, base_len + 2), charset);
                    if (result_set.insert(s).second) {
                        result.push_back(s);
                    }
                }
                return result;
            }

            // 使用选定的组生成长字符串
            vector<string> result;
            set<string> result_set;
            const auto& group = hash_groups[selected_hash];

            while (result.size() < count) {
                string s;
                while (s.length() < base_len) {
                    s += RandChoice(group);
                }
                // 裁剪到接近 base_len 的长度
                if (s.length() > base_len) {
                    s = s.substr(0, base_len);
                }
                if (result_set.insert(s).second) {
                    result.push_back(s);
                }
            }

            return result;
        }
    };

    /*
    * 实用工具函数
    */

    /**
     * @brief 生成高精度浮点数（保留x位小数）
     * @details 该函数生成一个范围为[l, r]的高精度浮点数，保留x位小数。
     * @param l 范围下限
     * @param r 范围上限
     * @param x 小数位数
     * @return 返回一个保留x位小数的随机浮点数
     */
    long double RandX(long double l, long double r, int x) {
        long double scale = pow(10, x);
        return round(Rand<long double>(l * scale, r * scale)) / scale;
    }

    /**
     * @brief 生成高精度浮点数并打印
     * @details 该函数生成一个高精度浮点数，并根据verbose参数选择带文字描述或无文字描述的输出。
     * @param l 范围下限
     * @param r 范围上限
     * @param x 小数位数
     * @param verbose 是否输出带文字描述的版本，默认为true
     */
    void generate_and_print_randx(long double l, long double r, int x, bool verbose = true) {
        long double val = RandX(l, r, x);
        cout << (verbose ? "随机高精度浮点数 (保留 " + to_string(x) + " 位小数): " : "") << fixed << setprecision(x) << val << "\n";
    }

    /**
     * @brief 生成随机字符串
     * @details 该函数生成一个长度为len的随机字符串，字符从charset中随机选择。
     * @param len 字符串长度
     * @param charset 字符集，默认为小写字母
     * @return 返回一个随机字符串
     * @throws invalid_argument 如果长度len < 0
     */
    string RandString(int len, const string& charset = "abcdefghijklmnopqrstuvwxyz") {
        return StringGenerator::random(len, charset);
    }

    /**
     * @brief 生成随机字符串并打印
     * @details 该函数生成一个随机字符串，并根据verbose参数选择带文字描述或无文字描述的输出。
     * @param len 字符串长度
     * @param charset 字符集，默认为小写字母
     * @param verbose 是否输出带文字描述的版本，默认为true
     * @throws invalid_argument 如果长度len < 0
     */
    void generate_and_print_randstring(int len, const string& charset = "abcdefghijklmnopqrstuvwxyz", bool verbose = true) {
        string s = RandString(len, charset);
        cout << (verbose ? "随机字符串: " : "") << s << "\n";
    }

    /**
     * @brief 生成随机颜色（十六进制格式）
     * @details 该函数生成一个随机的十六进制颜色代码，格式为 #RRGGBB。
     * @return 返回一个随机颜色代码字符串
     */
    string RandColorHex() {
        char buf[8];
        snprintf(buf, sizeof(buf), "#%02X%02X%02X", (int)Rand(0LL, 255LL), (int)Rand(0LL, 255LL), (int)Rand(0LL, 255LL));
        return string(buf);
    }

    /**
     * @brief 生成随机颜色并打印
     * @details 该函数生成一个随机颜色代码，并根据verbose参数选择带文字描述或无文字描述的输出。
     * @param verbose 是否输出带文字描述的版本，默认为true
     */
    void generate_and_print_randcolor(bool verbose = true) {
        string color = RandColorHex();
        cout << (verbose ? "随机颜色 (十六进制): " : "") << color << "\n";
    }

    /*
    * 示例程序：展示如何使用上述功能生成数据
    */

    /**
     * @brief 展示所有数据生成功能的完整示例
     * @param verbose 是否显示详细描述
     * @param extreme 是否包含边界测试用例
     */
    void Example(bool verbose = true, bool extreme = false) {
        cout << (verbose ? "===== 数据生成器示例演示 =====\n" : "");

        // ===== 1. 树生成示例 =====
        cout << (verbose ? "\n1. 树结构生成示例：\n" : "");
        {
            // 常规测试用例
            Tree::generate_and_print_tree(5, Tree::RANDOM, Tree::EDGE_LIST, 1, 10, verbose);
            Tree::generate_and_print_tree(6, Tree::CHAIN, Tree::ADJ_LIST, 1, 100, verbose);
            Tree::generate_and_print_tree(4, Tree::STAR, Tree::PARENT_ARRAY, 1, 50, verbose);

            // 边界测试用例
            if (extreme) {
                cout << (verbose ? "\n[边界测试] 大树生成：\n" : "");
                Tree::generate_and_print_tree(100000, Tree::BINARY, Tree::EDGE_LIST, 1, 1e9, false);
            }
        }

        // ===== 2. 图生成示例 ===== 
        cout << (verbose ? "\n2. 图结构生成示例：\n" : "");
        {
            // 常规测试用例
            Graph::generate_and_print_random_graph(5, 7, Graph::EDGE_LIST, false, 1, 20, false, verbose);
            Graph::generate_and_print_random_graph(4, 6, Graph::TRIPLE_LINES, true, 1, 50, true, verbose);

            // 边界测试用例
            if (extreme) {
                cout << (verbose ? "\n[边界测试] 稠密图生成：\n" : "");
                Graph::generate_and_print_random_graph(1000, 499500, Graph::COLUMNAR, false, 1, 1e9, false, false);
            }
        }

        // ===== 3. 数组生成示例 =====
        cout << (verbose ? "\n3. 特殊数组生成示例：\n" : "");
        {
            // 常规测试用例
            Array::generate_and_print_permutation(5, 1, 5, verbose);
            Array::generate_and_print_unique(5, 1LL, 10LL, verbose);
            Array::generate_and_print_mountain(6, 0, 10, true, false, verbose);

            // 边界测试用例
            if (extreme) {
                cout << (verbose ? "\n[边界测试] 大规模山峰数组：\n" : "");
                Array::generate_and_print_mountain(6, 0, (int)1e9, true, true, verbose);
            }
        }

        // ===== 4. 高级功能示例 =====
        cout << (verbose ? "\n4. 高级功能示例：\n" : "");
        {
            // 128位整数
            cout << (verbose ? "128位随机整数: " : "");
            write(Rand128(1e18, 1e20));
            cout << "\n";

            // 高精度浮点数
            generate_and_print_randx(0.0, 1.0, 5, verbose);

            // 随机字符串
            generate_and_print_randstring(10, "ACGT", verbose); // DNA序列

            // 特殊测试用例
            if (extreme) {
                cout << (verbose ? "\n[压力测试] 超长随机字符串：\n" : "");
                generate_and_print_randstring(1000000, "01", false); // 1MB二进制数据
            }
        }

        // ===== 5. 连通性测试示例 =====
        cout << (verbose ? "\n5. 连通性测试示例：\n" : "");
        {
            auto edges = Graph::connected(10, 15, 1, 100);
            if (verbose) {
                cout << "连通图验证（边数=" << edges.size() << "）：\n";
                for (auto& e : edges) cout << e.u << "-" << e.v << "(" << e.w << ") ";
                cout << "\n";
            } else {
                for (auto& e : edges) cout << e.u << " " << e.v << " " << e.w << "\n";
            }
        }

        cout << (verbose ? "\n===== 示例演示结束 =====\n" : "");

        // 6. 哈希碰撞字符串示例
        cout << (verbose ? "\n6. 哈希碰撞字符串示例：\n" : "");
        {
            auto strings = StringGenerator::hack_hash_table(5, 10);
            if (verbose) cout << "哈希碰撞字符串：\n";
            for (const auto& s : strings) cout << s << "\n";
        }

        cout << (verbose ? "\n===== 示例演示结束 =====\n" : "");
    }

    void ZExample(bool extreme) {
        // 运行所有示例，带文字描述
        cout << "运行所有示例（带文字描述）：\n";
        Example(true, extreme);

        // 运行所有示例，无文字描述
        cout << "\n运行所有示例（无文字描述）：\n";
        Example(false, extreme);
    }
}

/**
 * @brief 主函数：运行示例并生成数据
 */
signed main() {
//  rad::ZExample(false) ; 

    return 0 ; 
}

随机数生成命名空间 rad

函数名 功能描述 参数说明 返回值 异常/限制
Rand<T>(l, r) 生成指定范围的随机整数 T l: 下限<br>T r: 上限 类型 T 的随机整数 static_assert 检查整数类型，确保 T 为整数类型
Rand<long double>(l, r) 生成指定范围的随机浮点数 long double l: 下限<br>long double r: 上限 long double 随机浮点数 无
Rand128(l, r) 生成128位随机整数 __int128 l: 下限<br>__int128 r: 上限 __int128 随机整数 需用 write() 输出，l 和 r 必须在 __int128 可表示范围内
Shuffle(v) 随机打乱容器元素 vector<T>& v: 待打乱的容器 无（原地修改） 无
RandChoice(v) 从容器中随机选择元素 const vector<T>& v: 非空容器 const T& 随机元素 runtime_error 如果容器为空
RandX(l, r, x) 生成保留 x 位小数的随机浮点数 long double l: 下限<br>long double r: 上限<br>int x: 小数位数 long double 随机浮点数 无，x 为负时可能截断为整数
RandString(len, charset) 生成指定长度的随机字符串 int len: 字符串长度<br>const string& charset: 字符集（默认小写字母） string 随机字符串 invalid_argument 如果 len < 0 或 charset 为空
RandColorHex() 生成随机十六进制颜色 无 string 格式 #RRGGBB 无

树生成器类 rad::Tree

函数名 功能描述 参数说明 返回值 异常/限制
generate(n, type, min_w, max_w) 生成指定类型的树 n: 节点数<br>type: 树类型<br>min_w: 边权下限<br>max_w: 边权上限 vector<Edge> 边列表 invalid_argument 如果 n ≤ 0 或 min_w > max_w
generate_and_print_tree(n, type, format, min_w, max_w, verbose) 生成并输出树 同 generate 增加：<br>format: 输出格式<br>verbose: 是否显示描述 无（输出到 stdout） 同 generate，format 必须为支持的枚举值

树类型枚举 Type

输出格式枚举 OutputFormat

图生成器类 rad::Graph

函数名 功能描述 参数说明 返回值 异常/限制
random(n, m, min_w, max_w, directed) 生成包含 n 个节点和 m 条边的完全随机图，边的端点和权值随机，不保证连通性 n: 节点数 (1 to n)<br>m: 边数<br>min_w/max_w: 边权范围<br>directed: 是否有向 vector<Edge> 边列表 invalid_argument 如果 n ≤ 0，或 m 超出理论最大值（有向：n*(n-1)，无向：n*(n-1)/2）
connected(n, m, min_w, max_w, directed) 生成保证连通的随机图，先生成一棵树（n-1 条边），再添加剩余边 同 random vector<Edge> 边列表 invalid_argument 如果 n ≤ 0，m < n-1（无法连通），或 m 超过最大值
DAG(n, m, min_w, max_w) 生成有向无环图 (DAG)，通过随机拓扑序确保无环 n: 节点数<br>m: 边数<br>min_w/max_w: 边权范围 vector<Edge> 边列表 invalid_argument 如果 n ≤ 0，m < 0，或 m > n*(n-1)/2
hack_spfa(n, k, min_w, max_w) 生成挑战 SPFA 算法的菊花链图，测试最坏时间复杂度 n: 节点总数<br>k: “花瓣”数（链的数量）<br>min_w/max_w: 边权范围 vector<Edge> 边列表 invalid_argument 如果 n < 3，k < 2，或每条链节点数不足
generate_and_print_random_graph(n, m, output_format, sorted, min_w, max_w, directed, verbose) 生成并打印随机图 同 random，增加：<br>output_format: 输出格式<br>sorted: 是否按边权排序<br>verbose: 是否带描述 无（输出到 stdout） 同 random
generate_and_print_graph(n, m, min_w, max_w, directed, verbose) 生成并打印连通图 同 connected，增加：<br>verbose: 是否带描述 无（输出到 stdout） 同 connected
generate_and_print_dag(n, m, min_w, max_w, verbose) 生成并打印有向无环图 (DAG) 同 DAG，增加：<br>verbose: 是否带描述 无（输出到 stdout） 同 DAG
generate_and_print_hack_spfa(n, k, min_w, max_w, verbose) 生成并打印挑战 SPFA 的菊花链图 同 hack_spfa，增加：<br>verbose: 是否带描述 无（输出到 stdout） 同 hack_spfa

输出格式枚举 OutputFormat

数组生成器类 rad::Array

函数名 功能描述 参数说明 返回值 异常/限制
permutation(n, l, r) 生成 l 到 r 的随机排列 n: 元素个数<br>l: 下限<br>r: 上限 vector<int> 随机排列 invalid_argument 如果 n ≤ 0 或 r - l + 1 < n
unique(n, min_v, max_v) 生成唯一元素数组 n: 元素个数<br>min_v: 最小值<br>max_v: 最大值 vector<T> 唯一元素数组 invalid_argument 如果 n ≤ 0 或值域 (max_v - min_v + 1) < n
mountain(n, min_val, max_val, is_peak_max, strict) 生成山峰或山谷数组（先增后减或先减后增，可选严格单调） n: 元素个数<br>min_val/max_val: 值域<br>is_peak_max: 峰值最大（true 为先增后减）<br>strict: 是否严格单调 vector<int> 山峰或山谷数组 invalid_argument 如果 n ≤ 0，n < 2，或值域不足
generate_and_print_permutation(n, l, r, verbose) 生成并打印随机排列 同 permutation，增加：<br>verbose: 是否带描述 无（输出到 stdout） 同 permutation
generate_and_print_unique(n, min_v, max_v, verbose) 生成并打印唯一元素数组 同 unique，增加：<br>verbose: 是否带描述 无（输出到 stdout） 同 unique
generate_and_print_mountain(n, min_val, max_val, is_peak_max, strict, verbose) 生成并打印山峰或山谷数组 同 mountain，增加：<br>verbose: 是否带描述 无（输出到 stdout） 同 mountain

字符串生成器类 rad::StringGenerator

函数名 功能描述 参数说明 返回值 异常/限制
random(len, charset) 生成指定长度的随机字符串 len: 字符串长度<br>charset: 字符集（默认大小写字母） string 随机字符串 invalid_argument 如果 len < 0 或 charset 为空
random_list(count, min_len, max_len, charset) 生成随机字符串列表，字符串长度在 [min_len, max_len] 范围内 count: 字符串数量<br>min_len/max_len: 长度范围<br>charset: 字符集 vector<string> 随机字符串列表 invalid_argument 如果 count < 0，min_len < 0，max_len < min_len
hack_hash_table(count, base_len, charset) 生成一组导致哈希碰撞的字符串，用于测试哈希表性能 count: 字符串数量<br>base_len: 目标长度<br>charset: 字符集 vector<string> 碰撞字符串 runtime_error 如果无法在字符集中找到碰撞块

辅助函数

函数名 功能描述 参数说明 返回值 备注
read() 读取128位整数 无 __int128 支持负数输入
write(x) 输出128位整数 __int128 x: 要输出的数 无 支持负数输出
generate_and_print_randx(l, r, x, verbose) 生成并打印保留 x 位小数的随机浮点数 l: 下限<br>r: 上限<br>x: 小数位数<br>verbose: 是否带描述 无（输出到 stdout） 无
generate_and_print_randstring(len, charset, verbose) 生成并打印随机字符串 len: 字符串长度<br>charset: 字符集<br>verbose: 是否带描述 无（输出到 stdout） 同 RandString
generate_and_print_randcolor(verbose) 生成并打印随机十六进制颜色 verbose: 是否带描述 无（输出到 stdout） 无

造数据模板