【模板库】仙人掌生成

生成仙人掌，输出最短路的询问

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;

const int N = 10000;
const int Q = 10000;
const int INF = 10000;
const int block = 200;
const int MAXN = 100000;

int ord[MAXN],tmp,cnt,TMP;
vector<pair<int,int> > que;

inline int R(int lim) {
	if (!lim) return 0;
	else return rand()%lim+1;
}

int main(){
	srand(time(0));
	int n = N, q=R(Q);
	for (int i=1;i<=n;i++) ord[i] = i;
 	for (int i=1;i<=n;i++) swap(ord[R(n)],ord[R(n)]);
 	for (int i=1;i<=n;) {
		int len = min(R(n/block)+2,n-i+1);
		for (int j=0;j<len-1;j++) que.push_back(make_pair(ord[i+j],ord[i+j+1]));
		if (len > 2) que.push_back(make_pair(ord[i],ord[i+len-1]));
		if (tmp) que.push_back(make_pair(ord[i+R(len)-1],tmp));
		tmp = ord[i+R(len)-1]; i += len; 
	} cnt = que.size();
	printf("%d %d %d\n",n,cnt,q);
	for (int i=0;i<cnt;i++) {
		int a = que[i].first;
		int b = que[i].second;
		int c = R(INF);
		printf("%d %d %d\n",a,b,c);
	}
	for (int i=1;i<=q;i++) 
		cout<<R(n)<<' '<<R(n)<<endl;
	return 0;
}