UVA10603倒水问题+隐式图搜索-白红宇

UVA10603倒水问题+隐式图搜索

阅读量：4618 次

发布时间：2019-06-09

本文共 1863 字，大约阅读时间需要 6 分钟。

1 /*倒水问题UVA10603: 2 隐式图搜索： 3 我觉得解决这类问题，有几点很重要： 4 1、状态的表示（压缩状态表示可以减小空间复杂度） 5 2、时间复杂度（状态数）的正确评估，你要保证暴力法是可以解决的。换句话说，状态很快会被填满 6 3、编码的细心程度（废话，不过算法简单的话，对编码的要求自然就高了很多） 7 显然，这道题的状态上限是200*200，因为a'+b'+c'=c也可以简化状态的表示 8 */ 9 #include 
     
      10 #include 
      
       11 #include 
       
        12 #include 
        
         13 #include 
         
          14 #include 
          
           15 #include 
           
            16 #include 
            
             17 #include 
             
              18 #include 
              
               19 #include 
               
                20 #include 
                21 #include 
                 
                  22 #include 
                  
                   23 #include 
                   
                    24 #define INF 1e1025 #define maxn 200+1026 27 using namespace std;28 int a,b,c,d;29 int dt[maxn];//d==i是对应的最少倒水量30 bool mark[maxn][maxn];//记录状态的节点，以a和b的水量就可以了31 struct Node32 {33 int a,b,c,t;//t是总倒水量34 // Node(){a=0,b=0,c=0,t=0;}35 };36 void solve()37 {38 memset(mark,0,sizeof(mark));39 for(int i=0;i<=d;i++) dt[i]=INF;40 queue
                    
                     Q;41 Q.push((Node){ 0,0,c,0});42 while(!Q.empty())43 {44 Node no=Q.front();45 Q.pop();46 int a1=no.a,b1=no.b,c1=no.c,t1=no.t;47 dt[a1]=min(dt[a1],t1);dt[b1]=min(dt[b1],t1);dt[c1]=min(dt[c1],t1);48 int na,nb,nc,nt;49 if (mark[a1][b1]) continue;50 mark[a1][b1]=true;51 //a->b52 int rb=b-b1;53 if (a1>=rb) {nb=b;na=a1-rb;nt=t1+rb; Q.push((Node){na,nb,c1,nt});}54 else if (a1
                     
                      a56 int ra=a-a1;57 if (b1>=ra) {na=a;nb=b1-ra;nt=t1+ra; Q.push((Node){na,nb,c1,nt});}58 else if (b1
                      
                       c60 int rc=c-c1;61 if (a1>=rc) {nc=c;na=a1-rc;nt=t1+rc; Q.push((Node){na,b1,nc,nt});}62 else if (a1
                       
                        a64 ra=a-a1;65 if (c1>=ra) {na=a;nc=c1-ra;nt=t1+ra; Q.push((Node){na,b1,nc,nt});}66 else if (c1
                        
                         c68 rc=c-c1;69 if (b1>=rc) {nc=c;nb=b1-rc;nt=t1+rc; Q.push((Node){a1,nb,nc,nt});}70 else if (b1
                         
                          b72 rb=b-b1;73 if (c1>=rb) {nb=b;nc=c1-rb;nt=t1+rb; Q.push((Node){a1,nb,nc,nt});}74 else if (c1
                          
                           >t;82 while(t--){83 scanf("%d%d%d%d",&a,&b,&c,&d);84 solve();85 int maxd=-1;86 for(int i=d;i>=0;i--)87 if (dt[i]