生成一棵树

出数据时总会用到。。。自己yy了一个写法不知道肿么样。。。QAQ，而且节点无法确定只是近似值QAQ

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<ctime>
 6 using namespace std;
 7 const int maxn=100000+10;
 8 struct Tedge{int x,y,next;}adj[maxn*2];int ms=0,fch[maxn];
 9 void AddEdge(int u,int v){adj[++ms]=(Tedge){u,v,fch[u]};fch[u]=ms;return;}
10 int f[maxn][2];
11 inline int read(){
12     int x=0,sig=1;char ch=getchar();
13     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
14     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
15     return x*sig;
16 }
17 inline void write(int x){
18     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
19     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
20     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
21 }
22 int n,tot=1;
23 void make_tree(int u,int num){
24     if(num==1) {;return;}
25     if(num==0) {tot--;return;}
26     int tp=rand()%3+1;
27     if(tp>=num) tp=2;
28     int all=num,odd=num/tp,i;
29     for(i=1;i<tp;i++){
30         AddEdge(u,++tot);
31         printf("%d->%d
",u,tot);
32         all-=odd;
33         make_tree(tot,odd);
34     }
35     if(i<=tp){
36         AddEdge(u,++tot);
37         printf("%d->%d
",u,tot);
38         make_tree(tot,all);
39     }
40     return;
41 }
42 void make(int n){
43     srand(time(0));
44     make_tree(1,n/2);
45 }
46 void init(){
47     make(6);
48     return;
49 }
50 void work(){
51     return;
52 }
53 void print(){
54     return;
55 }
56 int main(){
57     init();work();print();return 0;
58 }

补。。。楼下标准生成一棵树：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<queue>
 6 #include<ctime>
 7 #define Rand rand()*rand()%1000000
 8 using namespace std;
 9 const int maxn=1100000;
10 struct Edge{
11     int a,b;
12     int r;
13     bool operator < (const Edge& ths) const{return r<ths.r;}
14 }e[maxn];
15 struct HeapNode{
16     int a,r;
17     bool operator < (const HeapNode& ths) const{return r<ths.r;}
18 };
19 priority_queue<HeapNode> Q1,Q2;
20 int use[maxn];
21 int main(){
22     int n,len;
23     printf("请输入N的值：");
24     cin>>n;
25     printf("是否有权值 t:是 0：不是
");
26     int t;
27     cin>>t;
28     printf("请输入文件名：
");
29     char s[25];
30     cin>>s;
31     len=strlen(s);
32     char filein[34];
33     sprintf(filein,"%s0.in",s);
34     cout<<filein<<endl;
35     srand(time(0));
36     for(int T=0;T<1;T++){
37         filein[len]=T+'0';
38         freopen(filein,"w",stdout); 
39         int k;
40         if(n<=10000) k=Rand%((n-1)*n/2)+1;
41         else k=Rand;
42         cout<<n<<" "<<n<<endl;
43         for(int i=0;i<n;i++) printf("%d
",Rand);
44         memset(use,0,sizeof(use));
45         Q1.push((HeapNode){1,rand()});
46         for(int i=2;i<=n;i++) Q2.push((HeapNode){i,rand()});
47         int m;
48         for(m=1;m<n;m++){
49             HeapNode from=Q2.top(); Q2.pop();
50             HeapNode to=Q1.top(); Q1.pop();
51             e[m]=(Edge){from.a,to.a,rand()};
52             Q1.push((HeapNode){to.a,rand()});
53             Q1.push((HeapNode){from.a,rand()});
54         }
55         sort(e+1,e+m);
56         for(int i=1;i<m;i++){
57             printf("%d %d",e[i].a,e[i].b);
58             if(t) printf(" %d",Rand%t+1);
59             putchar('
');
60         }
61         for(int i=1;i<=n;i++){
62             int t=rand()%3+1;printf("%d %d",t,Rand%n+1);
63             if(t!=3) printf(" %d",Rand);
64             printf("
");
65         }
66         while(!Q1.empty()) Q1.pop();
67         while(!Q2.empty()) Q2.pop();
68     }
69     return 0;
70 }