应吴老师之邀，写了个数据生成器。

目前这个数据生成器可以保证生成的数据都是合法的，且效率也还不错。只是在建立普通连通图的时候zyy偷懒了，直接把所有点串起来从而保证图的连通。如果有大神有更好的方法请不吝指教，zyy不胜感谢~~

下面是代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 #define MAXN 40
9 #define MAXM 100
10
11 int A[MAXN+10][MAXN+10];
12 int d[MAXN+10];
13
14 int n, m;
15
16 int GetRand(int L, int R)
17 {
18 int Len = R - L + 1;
19 int Ret = rand() * rand() % Len + L;
20 return Ret;
21 }
22
23 inline void Addedge(int u,int v,int o)
24 {
25 A[u][v]+=o;A[v][u]+=o;
26 d[u]+=o;d[v]+=o;
27 m+=o;
28 }
29
30 void gen()
31 {
32 int i, j, k, t;
33 bool Again;
34 memset(A, 0, sizeof(A));
35 memset(d, 0, sizeof(d));
36 for(i=1;in)
81 {
82 for(k=i+1;k<=n;k++) 83 { 84 if(d[k]) 85 break; 86 } 87 t=k;//找一个度为奇数的顶点t 88 for(k=1;k=i)//需要重新调整
99 {
100 for(t=1;t<=n;t++)//连接i与任意一个不相连的顶点t 101 { 102 if(!A[t][i]&&i!=t) 103 { 104 Addedge(t,i,1); 105 Again=true; 106 break; 107 } 108 } 109 if(t>n)//如果找不到这样的t，在确保图的连通的条件下删掉一条边
110 {
111 for(t=1;t<=n;t++) 112 { 113 if(d[t]>1)
114 {
115 Addedge(t,i,-1);
116 Again=true;
117 break;
118 }
119 }
120 }
121 }
122 if(Again)
123 i=0;
124 }
125 }
126 }
127 }
128
129
130 int main()
131 {
132 //freopen("data4.in","w",stdout);
133 srand(time(NULL));
134 int cas =10000;//GetRand(1, 1);
135 int i,j;
136 printf("%d\n", cas);
137 while(cas-- > 0)
138 {
139 n = GetRand(MAXN/5*3, MAXN);
140 m = GetRand(MAXM/5*3, MAXM);
141 gen();
142 printf("%d\n", m);
143 for(i=1;i0)
146 printf("%d %d\n",i,j);
147 }
148 return 0;
149 }