作为金牌教练，我为你准备了一个全自动化的数据生成系统。它不仅能生成符合 NOI 竞赛标准的 .in 文件，还会自动运行标准代码生成对应的 .out 答案文件。

数据生成器设计思路

1. 覆盖性：包含随机图、链状图（深树）、星形图（浅树）、完全不连通森林、带重边和自环。
2. 效率与规模：为了控制文件大小在 2MB 左右，我们将最大边数 $M$ 控制在 $10^5$ 左右（每行约 20 字节，10万行即约 2MB）。
3. 鲁棒性：并查集采用迭代版路径压缩，彻底杜绝在深链数据下的爆栈风险。
4. 随机性：使用 C++11 的 mt19937 高性能随机数引擎。

C++ 数据生成器完整代码

你可以直接编译并运行此代码，它会在当前目录下生成 1.in 到 10.out。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <ctime>

using namespace std;

// --- 算法标准实现部分 (用于生成 .out) ---
struct Edge {
    int u, v, w;
};

struct DSU {
    vector<int> fa;
    DSU(int n) {
        fa.resize(n + 1);
        for (int i = 1; i <= n; ++i) fa[i] = i;
    }
    // 迭代版路径压缩，防止爆栈
    int find(int x) {
        int root = x;
        while (fa[root] != root) root = fa[root];
        while (fa[x] != root) {
            int next = fa[x];
            fa[x] = root;
            x = next;
        }
        return root;
    }
    bool unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            fa[rootX] = rootY;
            return true;
        }
        return false;
    }
};

string solve(int n, int m, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });
    DSU dsu(n);
    long long mst_weight = 0;
    int cnt = 0;
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst_weight += e.w;
            cnt++;
        }
    }
    if (cnt == n - 1) return to_string(mst_weight);
    else return "orz";
}

// --- 数据生成逻辑部分 ---
mt19937 rng(time(0));

long long randW(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}

void generate_case(int id, int n, int m, string type) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fin(in_name);
    
    vector<Edge> edges;
    if (type == "small_connected") {
        for (int i = 2; i <= n; ++i) edges.push_back({i, (int)randW(1, i-1), (int)randW(1, 100)});
        while (edges.size() < m) edges.push_back({(int)randW(1, n), (int)randW(1, n), (int)randW(1, 100)});
    } 
    else if (type == "disconnected") {
        // 分成两个互不相连的块
        int mid = n / 2;
        for (int i = 2; i <= mid; ++i) edges.push_back({i, (int)randW(1, i-1), (int)randW(1, 1000)});
        for (int i = mid + 2; i <= n; ++i) edges.push_back({i, (int)randW(mid+1, i-1), (int)randW(1, 1000)});
    }
    else if (type == "chain") {
        for (int i = 1; i < n; ++i) edges.push_back({i, i + 1, (int)randW(1, 1e9)});
    }
    else if (type == "star") {
        for (int i = 2; i <= n; ++i) edges.push_back({1, i, (int)randW(1, 1e9)});
    }
    else if (type == "large_random") {
        // 生成随机生成树保证连通
        for (int i = 2; i <= n; ++i) edges.push_back({i, (int)randW(1, i-1), (int)randW(1, 1e9)});
        while (edges.size() < m) edges.push_back({(int)randW(1, n), (int)randW(1, n), (int)randW(1, 1e9)});
    }
    else if (type == "max_constraints") {
        for (int i = 2; i <= n; ++i) edges.push_back({i, (int)randW(1, i-1), 1000000000});
        while (edges.size() < m) edges.push_back({(int)randW(1, n), (int)randW(1, n), 1000000000});
    }

    // 打乱边序
    shuffle(edges.begin(), edges.end(), rng);
    
    fin << n << " " << edges.size() << "\n";
    for (auto& e : edges) fin << e.u << " " << e.v << " " << e.w << "\n";
    fin.close();

    // 生成答案
    ofstream fout(out_name);
    fout << solve(n, edges.size(), edges) << endl;
    fout.close();
    cout << "Test Case " << id << " [" << type << "] Generated." << endl;
}

int main() {
    // Case 1-2: 极小规模边界
    generate_case(1, 5, 4, "small_connected");
    generate_case(2, 10, 5, "disconnected");
    
    // Case 3-4: 特殊结构 (链与星)
    generate_case(3, 1000, 999, "chain");
    generate_case(4, 1000, 999, "star");

    // Case 5-6: 中等规模
    generate_case(5, 5000, 10000, "large_random");
    generate_case(6, 5000, 20000, "disconnected");

    // Case 7-10: 大规模压测 (为了控制2MB，M设定为80000~100000)
    generate_case(7, 100000, 80000, "disconnected"); // 森林
    generate_case(8, 100000, 90000, "large_random"); 
    generate_case(9, 100000, 100000, "max_constraints"); // 同权值测试
    generate_case(10, 100000, 100000, "large_random"); // 随机综合

    return 0;
}

测试点说明表

关键点提示

1. 文件大小控制：
   • 在测试点 10 中，$M=100,000$。每一行大约包含两个 6 位数和一个 10 位数，加上空格和换行约 22 字节。
   • $100,000 \times 22 \approx 2.1 \text{ MB}$。这在大多数 OJ 系统（如 Hydro, HUSTOJ, Vijos）的单文件上传限制内。如果你的 OJ 限制更严格（如 1MB），请将代码中最后几个 Case 的 $M$ 调小至 $40,000$。
2. 不连通情况：
   • 测试点 2, 6, 7 故意生成不连通图。Kruskal 算法必须通过计数已选边是否等于 $N-1$ 来准确输出 orz。
3. 防止爆栈：
   • 数据生成器中的 DSU 和生成的 solve 函数均采用了**非递归（迭代）**的 find 函数，这在处理 Case 3（深度为 1000 的链）时非常安全。