首页 > 代码库 > [数据生成器]UVA10054 The Necklace

[数据生成器]UVA10054 The Necklace

2024-07-10 09:29:07   218人阅读

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

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

 

下面是代码：

  1 #include<cstdio>  2 #include<ctime>  3 #include<cstring>  4 #include<cstdlib>  5 #include<cmath>  6 #include<vector>  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;i<n;i++)//保证图的连通 37     { 38         A[i][i+1]++;A[i+1][i]++; 39         d[i]++;d[i+1]++; 40     } 41     for(i=1;i<=m-n+1;i++)//剩下的边随机连接 42     { 43         do{ 44             j=GetRand(1,n); 45             k=GetRand(1,n); 46             if(j==k) continue; 47             A[j][k]++;A[k][j]++; 48             d[j]++;d[k]++; 49             break; 50         }while(true); 51     } 52     //调整边，使所有的顶点的度为偶数 53     for(i=1;i<=n;i++) 54     { 55         if(d[i]%2)//如果i点度为奇数，就再找一个度为奇数的点 56         { 57             for(j=i+1;j<=n;j++) 58             { 59                 if(d[j]%2) 60                 { 61                     if(A[i][j])//i、j之间有边 62                     { 63                         if(d[i]!=1&&d[j]!=1)//i、j之间不止一条边，则删掉一条边 64                         { 65                             Addedge(i,j,-1); 66                             break; 67                         } 68                         else 69                         { 70                             continue; 71                         } 72                     } 73                     else//i、j之间没有边，则连接i、j 74                     { 75                         Addedge(i,j,1); 76                         break; 77                     } 78                 } 79             } 80             if(j>n) 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;k++)//再找一个度为偶数的顶点k，若k与i、t不相连，则连接tk、ik 89                 { 90                     if(!A[t][k]&&!A[k][i]) 91                     { 92                         Addedge(t,k,1); 93                         Addedge(i,k,1); 94                         break; 95                     } 96                 } 97                 Again=false; 98                 if(k>=i)//需要重新调整 99                 {100                     for(t=1;t<=n;t++)//连接i与任意一个不相连的顶点t101                     {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;i<n;i++)144             for(j=i+1;j<=n;j++)145                 while(A[i][j]-->0)146                    printf("%d %d\n",i,j);147     }148     return 0;149 }
View Code

 


联系
我们