倒水问题 (FillUVa 10603) 隐式图

题意：本题的题意是给你三个杯子，第一二个杯子是空的，第三个杯子装满水，要求是量出一定容量d升的水。若是得不到d升的水，那就让某一个杯子里面的水达到d‘，使得d'尽量接近d升。

解题思路：本题是给出初始状态，让你寻找一条通往目标的路径，此题也可看成是有向图中在起点和目标点之间寻找一条最短路径，但是这个最短路径不是距离最短而是倒的水最少，所以这题类似于Dijkstra算法求最短路，利用广搜，一直选当前水量最少的结点进行扩展，所以可以建立一个优先队列来存储下一次要访问的结点，同时将访问过的结点标记一下，大大节省了访问时间，此题的结点数最多为201^2.

代码：

 #include<stdio.h>

 #include<math.h>

 #include<queue>

 #include<string.h>

 #include<iostream>

 using namespace std;

 const int maxn=;

 int n;

 int visit[maxn][maxn],cap[],ans[maxn];

 //三个数组分别表示标记是否访问过这种情况，三个容器的大小，以及得到对应的水需要倒水的体积

 struct Node{

     int v[],dist;

     const bool operator < (Node s) const{  //优先队列重载运算符

         return dist>s.dist;

     }

 };

 void update(Node t){        //更新倒水数

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

         int s=t.v[i];

         if(ans[s]< || t.dist<ans[s]){

             ans[s]=t.dist;

         }

     }

 }

 void traver(int a,int b,int c,int d){   //遍历函数

     priority_queue<Node> q;

     memset(visit,,sizeof(visit));

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

     cap[]=a;

     cap[]=b;

     cap[]=c;

     Node s;

     s.v[]=;

     s.v[]=;

     s.v[]=c;

     s.dist=;

     q.push(s);

     visit[][]=;

     while(!q.empty()){

         Node t=q.top();

         q.pop();

         update(t);

         if(ans[d]>=) break;

         for(int i=;i<;i++){//访问下一个结点,表示将水从i杯倒到j杯

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

                 if(i!=j){

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

                     Node k;

                     int water=min(t.v[i],cap[j]-t.v[j]);

                     k.dist=t.dist+water;

                     k.v[i]=t.v[i]-water;

                     k.v[j]=t.v[j]+water;

                     k.v[-i-j]=t.v[-i-j];          //如果不是讲原结点复制过来的，记得给此结点赋值

                     if(!visit[k.v[]][k.v[]]){

                         visit[k.v[]][k.v[]]=;

                         q.push(k);

                     }

                 }

             }

         }

     }

     for(;d>=;d--){　　　　//输出

         if(ans[d]>=){

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

             break;

         }

     }

 }

 int main(){

     freopen("in.txt","r",stdin);

     scanf("%d",&n);

     while(n--){

         int a,b,c,d;

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

         traver(a,b,c,d);

     }

     return ;

 }