data generator for oi

gen.cpp

//Data Generator Template
//WTFPL License
//by zzq
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define range(v) v.begin(),v.end()
#define SZ 666666
namespace rnd
{
namespace rnd_
{
unsigned z1,z2,z3,z4,b;
void srand_(unsigned x)
{z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
unsigned rand_()
{
	b=((z1<<6)^z1)>>13;
	z1=((z1&4294967294U)<<18)^b;
	b=((z2<<2)^z2)>>27;
	z2=((z2&4294967288U)<<2)^b;
	b=((z3<<13)^z3)>>21;
	z3=((z3&4294967280U)<<7)^b;
	b=((z4<<3)^z4)>>12;
	z4=((z4&4294967168U)<<13)^b;
	return (z1^z2^z3^z4);
}
struct ___ {___() {srand_(233333333);}}_____;
}
void srand(int seed) {rnd_::srand_(seed);}
int rand() {return rnd_::rand_()&32767;}
int br() {return (rand()<<15)+rand();}
double rd() {return rand()/32767.0;}
int randr(int r) {return br()%r;}
template<class T>
T randlr(T l,T r) {return l+br()%(r-l+1);}
template<class T>
void shuffle(T l,T r)
{
	for(T g=l;g!=r;g++) swap(*g,*(br()%(r-g)+g));
}
struct Graph
{
int n,M,fst[SZ],vb[SZ],nxt[SZ];
Graph() {M=0;}
void ad_de(int a,int b)
{
	++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b;
}
void adde(int a,int b)
{ad_de(a,b); ad_de(b,a);}
};
Graph* merge(Graph* a,Graph* b)
{
	Graph* tar=new Graph();
	tar->n=a->n+b->n;
	for(int i=1;i<=a->n;i++)
	{
		for(int e=a->fst[i];e;e=a->nxt[e])
		{
			int x=a->vb[e]; tar->ad_de(i,x);
		}
	}
	for(int i=1;i<=b->n;i++)
	{
		for(int e=b->fst[i];e;e=b->nxt[e])
		{
			int x=b->vb[e]; tar->ad_de(i+a->n,x+a->n);
		}
	}
	return tar;
}
Graph* chain(int n)
{
	Graph* tar=new Graph();
	tar->n=n;
	for(int i=2;i<=n;i++) tar->adde(i-1,i);
	return tar;
}
Graph* flower(int n)
{
	Graph* tar=new Graph();
	tar->n=n;
	for(int i=2;i<=n;i++) tar->adde(1,i);
	return tar;
}
Graph* rndtree(int n)
{
	Graph* tar=new Graph();
	tar->n=n;
	for(int i=2;i<=n;i++) tar->adde(br()%(i-1)+1,i);
	return tar;
}
//c1=1 c2=0 chain
//c1=0 c2=1 flower
//c1=0 c2=0 random
Graph* tree(int n,double c1=0.4,double c2=0.3)
{
	Graph* tar=new Graph();
	int a=(n-1)*c1,b=(n-1)*c2;
	b=min(b,n-1-a);
	int c=n-1-a-b;
	tar->n=n;
	for(int i=2;i<=a+1;i++) tar->adde(i-1,i);
	for(int i=a+2;i<=a+b+1;i++) tar->adde(1,i);
	for(int i=n-c+1;i<=n;i++) tar->adde(br()%(i-1)+1,i);
	return tar;
}
Graph* rndgraph(int n,int m)
{
	Graph* tar=new Graph();
	tar->n=n;
	for(int i=1;i<=m;i++) tar->adde(br()%n+1,br()%n+1);
	return tar;
}
namespace cactus_gen
{
Graph *tar,*g;
void rp(int a,int b) {tar->adde(a,b);}
int dfs(int x,int f=0)
{
	vector<int> r,s;
	for(int e=g->fst[x];e;e=g->nxt[e])
	{
		int b=g->vb[e]; if(b==f) continue;
		int p=dfs(b,x);
		if(!p) continue;
		if(p==b) r.push_back(p);
		else s.push_back(p);
	}
	if(r.empty()&&s.empty())
	{
		if(rd()<0.3) return 0;
		return x; 
	}
	double cs=0.7;
	if(s.empty()) cs=0;
	if(r.empty()) cs=1;
	if(rd()<=0.8)
	{
		int c; double ac;
		if(rd()<=cs) c=s[rand()%s.size()], ac=0.6;
		else c=r[rand()%r.size()], ac=0.3;
		if(rd()<=ac) {rp(x,c); return 0;}
		return c;
	}
	if(rd()<0.3) return 0;
	return x;
}
}
//generate cactus from a given tree
Graph* cactus(Graph* baset)
{
	using namespace cactus_gen;
	tar=new Graph; *tar=*baset; g=baset;
	dfs(1); return tar;
}
vector<pii> edges(Graph* g)
{
	vector<pii> vec;
	for(int i=1;i<=g->n;i++)
	{
		for(int j=g->fst[i];j;j=g->nxt[j]) vec.pb(pii(i,g->vb[j]));
	}
	return vec;
}
void ope(int a,int b)
{printf("%d %d\n",a,b);}
void ope_viz(int a,int b)
{printf("%d--%d;\n",a,b);}
int gm(Graph* g,bool sg=0)
{
	if(sg) return g->M;
	return g->M/2;
}
template<class oper>
void op(Graph* g,oper t,bool sg=0)
{
	for(int i=1;i<=g->n;i++)
	{
		for(int j=g->fst[i];j;j=g->nxt[j])
		{
			int b=g->vb[j]; if(sg||b>=i) t(i,b);
		}
	}
}
int __tmp__[SZ];
template<class oper>
void opr(Graph* g,oper t,bool sg=0)
{
	for(int i=1;i<=g->n;i++) __tmp__[i]=i;
	vector<pii> vs;
	shuffle(__tmp__+1,__tmp__+1+g->n);
	for(int i=1;i<=g->n;i++)
	{
		for(int j=g->fst[i];j;j=g->nxt[j])
		{
			int b=g->vb[j];
			if(sg||b>=i)
			{
				if((rand()&1)||sg) vs.pb(pii(__tmp__[i],__tmp__[b]));
				else vs.pb(pii(__tmp__[b],__tmp__[i]));
			}
		}
	}
	shuffle(range(vs));
	for(int i=0;i<vs.size();i++) t(vs[i].fi,vs[i].se);
}
void opev(int a,int b,ll c)
{printf("%d %d %lld\n",a,b,c);}
void opev_viz(int a,int b,ll c)
{printf("%d--%d[label=%lld];\n",a,b,c);}
struct Graphv: public Graph
{
	ll vc[SZ];
	void ad_de(int a,int b,ll c)
	{
		++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b; vc[M]=c;
	}
	void adde(int a,int b,ll c) {ad_de(a,b,c); ad_de(b,a,c);}
};
Graphv* cpyg(Graph* g)
{
	Graphv* tar=new Graphv();
	tar->n=g->n; tar->M=g->M;
	memcpy(tar->fst,g->fst,sizeof(tar->fst));
	memcpy(tar->vb,g->vb,sizeof(tar->vb));
	memcpy(tar->nxt,g->nxt,sizeof(tar->nxt));
	return tar;
}
template<class rander>
Graphv* randv(Graph* g,rander rr)
{
	Graphv* tar=cpyg(g);
	for(int i=1;i<=g->M;i++) tar->vc[i]=rr();
	return tar;
}
template<class oper>
void opv(Graphv* g,oper t,bool sg=0)
{
	for(int i=1;i<=g->n;i++)
	{
		for(int j=g->fst[i];j;j=g->nxt[j])
		{
			int b=g->vb[j]; if(b>=i||sg) t(i,b,g->vc[j]);
		}
	}
}
template<class oper>
void oprv(Graphv* g,oper t,bool sg=0)
{
	for(int i=1;i<=g->n;i++) __tmp__[i]=i;
	vector<pair<pii,int> > vs;
	shuffle(__tmp__+1,__tmp__+1+g->n);
	for(int i=1;i<=g->n;i++)
	{
		for(int j=g->fst[i];j;j=g->nxt[j])
		{
			int b=g->vb[j];
			if(b>=i||sg)
			{
				if((rand()&1)||sg) vs.pb(mp(pii(__tmp__[i],__tmp__[b]),g->vc[j]));
				else vs.pb(mp(pii(__tmp__[b],__tmp__[i]),g->vc[j]));
			}
		}
	}
	shuffle(range(vs));
	for(unsigned i=0;i<vs.size();i++) t(vs[i].fi.fi,vs[i].fi.se,vs[i].se);
}
Graph* rgraph(int n,int m,bool sg=0)
{
	Graph* tar=new Graph(); tar->n=n;
	while(m--)
	{
		int a=br()%n+1,b=br()%n+1;
		if(sg) tar->ad_de(a,b);
		else tar->adde(a,b);
	}
	return tar;
}
//no self-cycle and multi-edge
Graph* rsgraph(int n,int m,bool sg=0)
{
	set<pii> sp;
	Graph* tar=new Graph(); tar->n=n;
	while((int)sp.size()!=m)
	{
		int a=rand()%n+1,b=rand()%n+1;
		if(a==b) continue;
		if(a>b&&!sg) swap(a,b);
		if(sp.find(pii(a,b))!=sp.end()) continue;
		sp.insert(pii(a,b));
		if(sg) tar->ad_de(a,b);
		else tar->adde(a,b);
	}
	return tar;
}
Graph* stair(int n)
{
	Graph* tar=new Graph(); tar->n=n+n;
	for(int i=1;i<n;i++)
	{
		tar->adde(i,i+1);
		tar->adde(i+n,i+n+1);
	}
	for(int i=1;i<=n;i++) tar->adde(i,i+n);
	return tar;
}
Graph* grid(int n,int m)
{
	Graph* tar=new Graph(); tar->n=n*m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(j) tar->adde(i*m+j+1,i*m+j);
			if(i) tar->adde(i*m+j+1,(i-1)*m+j+1);
		}
	}
	return tar;
}
//hack spfa
Graph* kspfa(int n,int c=2)
{
	Graph* p=stair(n/2);
	for(int i=1;i<=c;i++)
	p->adde(br()%p->n+1,br()%p->n+1);
	return p;
}
/*
It's recommended to write codes in this namespace.
Because it will override default rand/srand.
(If you only use 'using namespace rnd' outside,
you have to type rnd::rand & rnd::srand)
Usage:
rand() random number in [0,32768)
br() random number in [0,1073741824)
rd() random double in [0,1]
randr(x) random number in [0,x)
randlr(l,r) random number(pointer/iterator?) in [l,r]
shuffle(l,r)=random_shuffle(l,r)
make a graph: Graph* s=new Graph(); s->n=n;
use ad_de or adde to add an edge in a graph.
print a graph:
op(s,ope) for non-directed graph
op(s,ope,1) for directed graph
use opr instead of op will randomize the graph (recommended):
opr(s,ope) for non-directed graph
opr(s,ope,1) for directed graph
make a tree: (non-directed)
rndtree(n) a random tree with n points
tree(n) a strong tree (better output with opr)
tree(n,0.7,0.1) a very strong tree: 70%chain, 10%flower
make a cactus:
cactus(tree)
it will add some edges from a tree to form a cactus
make a random graph:
rgraph(n,m)
make a non-directed random graph with n vertexes, m edges
rgraph(n,m,1)
make a random graph without parallel edges or self-cycle:
rsgraph(n,m,0/1) too lazy to explain again
make a directed random graph with n vertexes, m edges
also there are graphs with vals: Graphv
make a graphv: Graphv* s=new Graphv(); s->n=n;
create a graphv from a graph with random value:
randv(graph,random_number_generator)
you may use anything like rand(), br().
output a graphv:
opv/oprv (s,ope,0/1) see op/opr above
something (useless):
stair(n): a 2*n stair graph
grid(n,m): a n*m grid graph
kspfa(n):
a graph with <=n vertexes that may make spfa slow
*/
//example below
namespace example
{
//#include <windows.h>
int myrand() {return br()%100000+1;}
void gen()
{
	int n; cin>>n;
	//srand(GetTickCount());
	srand(time(0));
	cout<<n<<" "<<n-1<<"\n";
	oprv(randv(tree(n,0.6,0.1),myrand),opev);
}
}
}
int main()
{
	rnd::example::gen();
}