感谢 @TheWorld
我们可以写一个cpp的对拍
要保证对拍中出现的所有文件和对拍文件在同一文件夹中
#include <bits/stdc++.h>
using namespace std;
signed main()
{
while (true)
{
system("data>input.txt");
system("main<input.txt>output.txt");
system("std<input.txt>stdout.txt");
if (system("FC output.txt stdout.txt"))
break;
}
system("pause");
}
data.exe : 用于生成数据
input.txt : 用于保存生成的数据
main.exe : 我们的程序
std.exe : 我们写的暴力程序
outout.txt : 保存我们自己写的程序的输出
stdout.txt : 保存我们暴力代码的输出
(所有的exe文件都由.cpp生成)
其中所有的文件名我们都可以用字符串提前进行保存
对拍数据生成
生成0~n-1的随机数据
typedef long long LL;
int random(int n)
{
return (LL)rand() * rand() * 3 % n;
}
生成绝对值小于等于n的数
cout << random(2 * n + 1) - n;
生成[1,n]的子区间
int l = random(n) + 1;
int r = random(n) + 1;
if(l > r) swap(l, r);
cout << l << " " << r << endl;
生成n个点,n-1条边,边权为[1,1e9]的树
for(int i = 2; i <= n; i ++ )
{
int fa = random(i-1) + 1;
int val = random(1e9) + 1;
cout << fa << " " << i << " " << val << endl;
}
生成一张图
pair<int, int> e[1e6 + 10];
map<pair<int, int>, bool> h;
for(int i = 2; i <= n; i ++ )
{
int fa = random(i - 1) + 1;
e[i] = make_pair(fa, i);
h[e[i]] = h[make_pair(i, fa)] = 1;
}
for(int i = n; i <= m; i ++ )
{
int x, y;
do
{
x = random(n) + 1, y = random(n) + 1;
}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);
for(int i = 1; i <= m; i ++ )
cout << e[i].first << " " << e[i].second << endl;
参考博主的:图的生成修改如下:
3、图的生成
图的生成,可以参照树的生成。本质上树也是一种图。
原理:
#include<bits/stdc++.h> using namespace std; typedef long long LL; pair<int, int> e[1000000];//有边的点对 map<pair<int, int>, bool> h;//点对,是否存在过,本质是一个hash //生成0~n-1的随机数 int random(int n) { return (LL)rand() * rand() * 3 % n; } //n个点,m条边的图,点的编号从0开始 int main(){ srand(time(0)); int n,m; cin >> n>> m; //生成n-1条边的树 for(int i = 2; i <= n; i ++ ) { //fa编号 < i的编号 int fa = random(i - 1) + 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(n) + 1, y = random(n) + 1; }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); //让点对随机一下 for(int i = 1; i <= m; i ++ ) cout << e[i].first << " " << e[i].second << endl; return 0; }
图的生成那边,有个下标的问题。
for(int i = 2; i <= n; i ++ ) { int fa = random(i - 1) + 1; e[i] = make_pair(fa, i); //这里e[i]应该改为e[i-1],因为e代表有边的点对,下标是从1开始,这里是从2开始 h[e[i]] = h[make_pair(i, fa)] = 1;//这里一样改为e[i-1] }
总体上,这篇分享非常好。非常受用,感谢博主。