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));
for(int i = 1; i <= n; ++i) 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));
for (int i = 2; i <= n; ++i) printf("%d %d\n", i, RAND(i - 1));
}

2、以任意结点为根的树

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

四、随机生成图
1、连通图
先构造一棵树,再随意加边
2、普通图
随便加边就可以了
3、无重边
用set记录二元组
4、无自环
起点终点不一致即可
5、DAG
随机一个排列作为拓扑序,然后随机从前面的点加边到后面
6、无大环套小环
每个点至多一个出度

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