poj 1465 Multiple（bfs+余数判重）

题意：给出m个数字，要求组合成能够被n整除的最小十进制数。

分析：用到了余数判重，在这里我详细的解释了。其它就没有什么了。

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 const int N=;

 struct Node{

     int pre;

     int r;

     int d;

 };

 int vis[MAXN];

 int num[N];

 int n,c,m;

 Node q[MAXN];

 void print(int x)

 {

     if(q[x].pre==-)

         return ;

     print(q[x].pre);

     printf("%d",q[x].d);

 }

 int bfs()

 {

     memset(vis,,sizeof(vis));

     int dl,dr;

     dl=dr=;

     Node u,v;

     u.pre=-;

     u.d=;

     u.r=;

     q[dr++]=u;

     vis[]=;

     int ok=;

     while(dl<dr)

     {

         u=q[dl++];

         for(int i=;i<m;i++)

         {

             int r=u.r*+num[i];

             if(r>=n&&r%n==){

                 print(dl-);

                 printf("%d\n",num[i]);

                 return ;

             }

             r=r%n;

             if(!vis[r]){

                 vis[r]=;

                 v.r=r;

                 v.d=num[i];

                 v.pre=dl-;

                 q[dr++]=v;

             }

         }

     }

     return -;

 }

 int main()

 {

     int T;

     while(~scanf("%d%d",&n,&m))

     {

         memset(num,-,sizeof(num));

         for(int i=;i<m;i++)

             scanf("%d",&num[i]);

         sort(num,num+m);

         if(n==)

             printf("0\n");

         else{

             int ans=bfs();

             if(ans==-)

                 printf("0\n");

         }

     }

     return ;

 }