OI中的常用数据生成

一、随机生成一个小于等于$n$的数

1
2
3
4
int RAND(int n) {
srand((int)time(0));
return rand()%n+1;
}

二、随机生成排列

1
2
3
4
5
6
7
int t[MAXN];
int mp(int n) {
int i;
srand((int)time(0));
fo (i, 1, n) t[i] = i;
random_shuffle(t+1, t+1+n);//STL的打乱数组函数
}

三、随机生成树
1、以1为根的树

1
2
3
4
5
int mt1(int n) {
int i;
srand((int)time(0));
fo (i, 2, n) printf("%d %d\n", i, RAND(i-1));
}

2、以任意结点为根的树

1
2
3
4
5
int mt2(int n) {
int i;
srand((int)time(0));
mp(n); fo (i, 2, n) printf("%d %d\n", t[i], t[RAND(i-1)]);
}

四、随机生成图
(如果不需要重边,用set,不需要自环,起点终点不一致即可)
1、连通图
先构造一棵树,再随意加边
2、普通图
随便加边就可以了

------ 本文结束 ------