状态空间搜索好题UVA10603

题目

分析：注意这里求的是最少流量， 二不是最少步数！！！所以我们用优先队列去维护一个最小流量，然后进行bfs即可，解释一下一个重要的数组ans[i],表示的是杯子中的水为i时的最小流量

 #include "iostream"

 #include "cstdio"

 #include "cstring"

 #include "queue"

 #include "algorithm"

 using namespace std;

 const int maxn=+;

 int a,b,c,d,T;

 int vis[maxn][maxn],ans[maxn],cap[];  //ans[i]表示杯子中有i升水时对应的最少倒水量

 struct Node{

     int v[],dist;

     bool operator < (const Node & rsh) const{  //小顶堆

         return dist>rsh.dist;

     }

 };

 void update(const Node & u){   //更新ans[]

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

         int s=u.v[i];

         if(ans[s]<||u.dist<ans[s])  ans[s]=u.dist;

     }

 }

 void bfs(int a,int b,int c,int d){

     memset(vis,,sizeof(vis));

     memset(ans,-,sizeof(ans));

     cap[]=a,cap[]=b,cap[]=c;

     Node start;

     start.dist=;

     start.v[]=,start.v[]=,start.v[]=c;

     priority_queue<Node>que;

     vis[][]=;

     que.push(start);

     while(!que.empty()){

         Node u=que.top(); que.pop();

         update(u);

         if(ans[d]>=)  break;   //如果找到了

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

             for(int j=;j<;j++) if(i!=j){   //自己不能和自己匹配

                 if(u.v[i]==||u.v[j]==cap[j])   continue;

                 int num=min(cap[j],u.v[i]+u.v[j])-u.v[j];

                 Node u2;

                 memcpy(&u2,&u,sizeof(u));

                 u2.v[i]-=num;

                 u2.v[j]+=num;

                 u2.dist=u.dist+num;

                 if(!vis[u2.v[]][u2.v[]]){  //如果当前状态没有出现过

                     vis[u2.v[]][u2.v[]]=;

                     que.push(u2);

                 }

             }

         }

     }

     while(d>=){

         if(ans[d]>=){

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

             return ;

         }

         --d;

     }

 }

 int main()

 {

     scanf("%d",&T);

     while(T--){

         scanf("%d%d%d%d",&a,&b,&c,&d);

         bfs(a,b,c,d);

     }

     return ;

 }