开发日志：
12.27：
根据李煜东小蓝书制作了一款随机数据生成器，目前支持数据类型：
A:生成长度为 n 整数序列。
B:生成 m 个 [1 , n] 的子区间。
C:生成一颗 n 个节点的无向树。
D:生成一幅 n 个节点, m 条边的无向图。
E:生成一幅 n 个节点的链, 加上 m 条边。
其中，C , D , E 可自行决定是否需要边权。
采用的随机数算法：梅森旋转（mt19937）, 循环节为 2^19937 次。
目前只支持整数上的均匀分布。
输出数据保存在 '输出.out' 文件中
点击查看代码
#include<bits/stdc++.h>
using namespace std;
bool isInit;
int index;
int MT[624]; //624 * 32 - 31 = 19937
void srand(int seed)
{
index = 0;
isInit = 1;
MT[0] = seed;
for(int i=1; i<624; i++)
{
int t = 1812433253 * (MT[i-1] ^ (MT[i-1] >> 30)) + i;
MT[i] = t & 0xffffffff; //取最后的32位
}
}
void generate()
{
for(int i=0; i<624; i++)
{
// 2^31 = 0x80000000
// 2^31-1 = 0x7fffffff
int y = (MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7fffffff);
MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
if (y & 1)
MT[i] ^= 2567483615;
}
}
int rand()
{
if(!isInit)
srand((int)time(NULL));
if(index == 0)
generate();
int y = MT[index];
y = y ^ (y >> 11);
y = y ^ ((y << 7) & 2636928640);
y = y ^ ((y << 15) & 4022730752);
y = y ^ (y >> 18);
index = (index + 1) % 624;
return y;
}
unsigned int rand4() { return rand() & 15; }
template <typename T>
T random(T l, T r){
typedef typename std::make_unsigned<T>::type U;
U u = r - l, g = 15, w = 0;
if(g == u) return l + rand4();
if(g > u){
U eu = u + 1, s = g / eu, t = s * eu;
do{
w = rand4();
}while(w >= t);
w /= s;
} else {
U eg = g + 1, s = u / eg;
do{
w = random((U)0, s) * eg + rand4();
}while(w >= u);
}
return l + w;
}
char the_need;
/*
'A' means make some Integer sequence.
'B' means make some Interval's left and right.
'C' means make some tree.
'D' means make some picture.
*/
void Integer_sequence() {
int n, left_m, right_m;
puts("请输入 n 的值:"); scanf("%d", &n);
puts("请输入元素范围，保证 left <= right. "); scanf("%d%d", &left_m, &right_m);
puts(""); freopen("输出.out", "w", stdout);
int a[n + 1];
memset(a, 0, sizeof a);
for (int i = 1; i <= n; i++) {
a[i] = random(left_m, right_m);
}
printf("%d\n", n);
for (int i = 1; i <= n; i++) {
printf("%d\n", a[i]);
}
}
void Interval_left_and_right() {
int n, m;
puts("请输入 n 的值:"); scanf("%d", &n);
puts("请输入 m 的值:"); scanf("%d", &m);
puts(""); freopen("输出.out", "w", stdout);
printf("%d %d\n", n, m);
for (int i = 1; i <= m; i++) {
int l = random(1, n);
int r = random(1, n);
if (r < l) swap(l, r);
printf("%d %d\n", l, r);
}
}
void tree() {
int n, left_m, right_m;
bool yes_or_no_of_val;
puts("请输入 n 的值:"); scanf("%d", &n);
puts("是否需要边权？");
puts("Yes : 1"); puts("No : 0"); scanf("%d", &yes_or_no_of_val);
if (yes_or_no_of_val) {
puts("请输入边权范围，保证 left <= right. ");
scanf("%d%d", &left_m, &right_m);
}
puts("");
freopen("输出.out", "w", stdout);
printf("%d\n", n);
for (int i = 2; i <= n; i++) {
int fa = random(1, i - 1);
printf("%d %d", fa, i);
if (yes_or_no_of_val) {
int val = random(left_m, right_m);
printf(" %d", val);
}
puts("");
}
}
void picture() {
int n, m, left_m, right_m;
bool yes_or_no_of_val;
puts("警告：请遵守数据范围。");
puts("请数据保持 5 <= n <= m <= n * (n - 1) / 4 <= 1e6 , 若溢出 m 自动等于上限");
puts("请输入 n 的值:"); scanf("%d", &n);
puts("请输入 m 的值:"); scanf("%d", &m);
if (m > n * (n - 1) / 4 || m < n - 1) m = n * (n - 1) / 4;
puts("是否需要边权？");
puts("Yes : 1"); puts("No : 0"); scanf("%d", &yes_or_no_of_val);
if (yes_or_no_of_val) {
puts("请输入边权范围，保证 left <= right. ");
scanf("%d%d", &left_m, &right_m);
} puts("");
freopen("输出.out", "w", stdout);
pair < int , int > e[m + 1];
map < pair < int , int > , bool > h;
memset(e, 0, sizeof e);
for (int i = 2; i <= n; i++) {
int fa = random(1, i - 1);
e[i - 1] = make_pair(fa, i);
h[e[i - 1]] = h[make_pair(i, fa)] = 1;
}
for (int i = n; i <= m; i++) {
int x, y;
do {
x = random(1, n);
y = random(1, n);
} while (x == y || h[make_pair(x, y)]);
e[i] = make_pair(x, y);
h[e[i]] = h[make_pair(y, x)] = 1;
}
random_shuffle(e + 1, e + m + 1);
int val[m]; memset(val, 0, sizeof val);
if (yes_or_no_of_val)
for (int i = 1; i <= m; i++)
val[i] = random(left_m, right_m);
printf("%d %d\n", n, m);
for (int i = 1; i <= m; i++) {
printf("%d %d", e[i].first, e[i].second);
if (yes_or_no_of_val) printf(" %d", val[i]);
puts("");
}
}
void chain() {
int n, m, left_m, right_m;
bool yes_or_no_of_val;
puts("警告：请遵守数据范围。");
puts("请数据保持 5 <= n <= m + n - 1 <= n * (n - 1) / 4 <= 1e6 , 若溢出 m 自动等于上限");
puts("请输入 n 的值:"); scanf("%d", &n);
puts("请输入 m 的值:"); scanf("%d", &m); m += n - 1;
if (m > n * (n - 1) / 4 || m < n - 1) m = n * (n - 1) / 4;
puts("是否需要边权？");
puts("Yes : 1"); puts("No : 0"); scanf("%d", &yes_or_no_of_val);
if (yes_or_no_of_val) {
puts("请输入边权范围，保证 left <= right. ");
scanf("%d%d", &left_m, &right_m);
} puts("");
freopen("输出.out", "w", stdout);
pair < int , int > e[m + 1];
bool vis[n + 1];
map < pair < int , int > , bool > h;
memset(e, 0, sizeof e);
memset(vis, 0, sizeof vis);
for (int i = 1; i < n; i++) {
int x;
do {
x = random(1, n);
} while (vis[x] || x == i || h[make_pair(x, i)]);
vis[x] = 1;
e[i] = make_pair(i, x);
h[e[i]] = h[make_pair(x, i)] = 1;
}
for (int i = n; i <= m; i++) {
int x, y;
do {
x = random(1, n);
y = random(1, n);
} while (x == y || h[make_pair(x, y)]);
e[i] = make_pair(x, y);
h[e[i]] = h[make_pair(y, x)] = 1;
}
random_shuffle(e + 1, e + m + 1);
int val[m]; memset(val, 0, sizeof val);
if (yes_or_no_of_val)
for (int i = 1; i <= m; i++)
val[i] = random(left_m, right_m);
printf("%d %d\n", n, m);
for (int i = 1; i <= m; i++) {
printf("%d %d", e[i].first, e[i].second);
if (yes_or_no_of_val) printf(" %d", val[i]);
puts("");
}
}
signed main() {
puts ("数据生成器1.0");
puts ("所有生成数据均在输出.out文件中");
puts ("—————————————————————");
puts ("A:生成长度为 n 整数序列");
puts ("B:生成 m 个 [1 , n] 的子区间");
puts ("C:生成一颗 n 个节点的无向树");
puts ("D:生成一幅 n 个节点, m 条边的无向图");
puts ("E:生成一幅 n 个节点的链, 加上 m 条边");
scanf("%c", &the_need);
if (the_need == 'A') Integer_sequence();
if (the_need == 'B') Interval_left_and_right();
if (the_need == 'C') tree();
if (the_need == 'D') picture();
if (the_need == 'E') chain();
return 0;
}