uva 10603 倒水问题

刘汝佳说这是一道最短路，可是我怎么也想不出如何建图，把问题转换为最短路问题，我就想自己的办法。感觉这个题可以用三维dp；每一维代表一个瓶子 f[maxn][maxn][maxn]；状态转移我就想：每一次倒水一定要把一个倒完或把另一个装满才有意义，因为只有这样三个瓶的水量才知道；所以可以根据这个进行状态转移。状态转移代码有点啰嗦，主要是不同维不能统一一个式子。最后想到用队列来存变化的状态。
  1 #include <cstdio>
  2 #include <cmath>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <queue>
  6 #include <cstring>
  7 #define maxn 205
  8 using namespace std;
  9 
 10 const int INF = 0x3f3f3f;
 11 
 12 int f[maxn][maxn][maxn];
 13 int maxi,maxj,maxk,maxd;
 14 struct node{
 15     int i,j,k;
 16 }Node;
 17 int i,j,k;
 18 int ansnum,ans;
 19 queue<node> Q;
 20 int T;
 21 void print(){
 22 
 23     printf("%d %d %d      %d %d %d     %d \n",i,j,k,Node.i,Node.j,Node.k,f[Node.i][Node.j][Node.k]);
 24 }
 25 
 26 int main()
 27 {
 28     //if(freopen("input.txt","r",stdin)== NULL)  {printf("Error\n"); exit(0);}
 29     //if(freopen("output.txt","w",stdout)== NULL)  {printf("Error\n"); exit(0);}
 30     cin>>T;
 31     while(T--){
 32         cin>>maxi>>maxj>>maxk>>maxd;
 33         memset(f,0x3f,sizeof(f));
 34         while(!Q.empty())  Q.pop();
 35         f[0][0][maxk] = 0;
 36         Node.i = 0;  Node.j = 0;  Node.k = maxk;
 37         Q.push(Node);
 38         while(!Q.empty()){
 39             Node = Q.front(); Q.pop();
 40             i = Node.i; j = Node.j;  k = Node.k;  
 41             
 42             if(i != maxi){
 43                if(j >= (maxi - i)){
 44                  Node.j = j - (maxi - i);  Node.i = maxi;  Node.k = k;
 45                  
 46                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + maxi - i){
 47                        f[Node.i][Node.j][Node.k] = f[i][j][k] + maxi - i;
 48                        Q.push(Node); 
 49                     }
 50                }
 51                   else{
 52                        Node.j = 0 ;  Node.i = j + i;  Node.k = k;
 53                  
 54                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + j){
 55                      f[Node.i][Node.j][Node.k] = f[i][j][k] + j;
 56                      Q.push(Node); 
 57                     }
 58                   }
 59                   if(k >= (maxi - i)){
 60                  Node.j = j;  Node.k = k - (maxi - i);  Node.i = maxi;
 61                  
 62                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + maxi - i){
 63                      f[Node.i][Node.j][Node.k] = f[i][j][k] + maxi - i;
 64                      Q.push(Node);  
 65                    }
 66                   }
 67                   else{
 68                        Node.j = j;  Node.i = k + i;  Node.k = 0;
 69                 
 70                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + k){
 71                      f[Node.i][Node.j][Node.k] = f[i][j][k] + k;
 72                      Q.push(Node);  
 73                     }
 74                   }
 75                 }
 76             if(j != maxj){
 77                if(i >= (maxj - j)){
 78                  Node.j = maxj;  Node.i = i - (maxj - j);  Node.k = k;
 79                  
 80                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + maxj - j){
 81                        f[Node.i][Node.j][Node.k] = f[i][j][k] + maxj - j;
 82                        Q.push(Node); 
 83                     }
 84                }
 85                   else{
 86                        Node.j = j + i;  Node.i = 0;  Node.k = k;
 87                  
 88                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + i){
 89                      f[Node.i][Node.j][Node.k] = f[i][j][k] + i;
 90                      Q.push(Node);  
 91                     }
 92                   }
 93                   if(k >= (maxj - j)){
 94                  Node.j = maxj;  Node.i = i;  Node.k = k - (maxj - j);
 95                 
 96                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + maxj - j){
 97                      f[Node.i][Node.j][Node.k] = f[i][j][k] + maxj - j;
 98                      Q.push(Node);  
 99                    }
100                   }
101                   else{
102                        Node.j = j + k;  Node.i = i;  Node.k = 0;
103                  
104                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + k){
105                      f[Node.i][Node.j][Node.k] = f[i][j][k] + k;
106                      Q.push(Node);  
107                     }
108                   }
109                 
110                }
111             
112             if(k != maxk){
113                if(i >= (maxk - k)){
114                  Node.j = j;  Node.k =maxk;  Node.i = i - (maxk - k);
115                  
116                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + maxk - k){
117                        f[Node.i][Node.j][Node.k] = f[i][j][k] + maxk - k;
118                        Q.push(Node);  
119                     }
120                }
121                   else{
122                        Node.j = j;  Node.i = 0;  Node.k = k + i;
123                  
124                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + i){
125                      f[Node.i][Node.j][Node.k] = f[i][j][k] + i;
126                      Q.push(Node);  
127                     }
128                   }
129                   if(j >= (maxk - k)){
130                  Node.k = maxk;  Node.j = j - (maxk - k);  Node.i = i;
131                 
132                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + maxk - k){
133                      f[Node.i][Node.j][Node.k] = f[i][j][k] + maxk - k;
134                      Q.push(Node);  
135                    }
136                   }
137                   else{
138                        Node.k = k + j;  Node.i = i;  Node.j = 0;
139                  
140                  if(f[Node.i][Node.j][Node.k] > f[i][j][k] + j){
141                      f[Node.i][Node.j][Node.k] = f[i][j][k] + j;
142                      Q.push(Node);  
143                     }
144                   }
145                 }
146         }
147         ans = 0;ansnum = INF;
148         for(int m = maxd;m>=0;m--){
149             for(int n = 0;n <= maxk - m ;n++){
150                 if(f[m][maxk - m - n][n] < ansnum){
151                     ans = m; ansnum = f[m][maxk - m - n][n]; 
152                 }
153                 if( ansnum > f[m][n][maxk - m - n]){
154                     ans = m; ansnum = f[m][n][maxk - m - n]; 
155                 }
156                 if(f[maxk - m - n][m][n] < ansnum){
157                     ans = m; ansnum =f[maxk - m - n][m][n];  
158                 }
159                 if(f[n][m][maxk - m - n] < ansnum){
160                     ans = m; ansnum =f[n][m][maxk - m - n];  
161                 }
162                 if(f[n][maxk - m - n][m] < ansnum){
163                     ans = m; ansnum =f[n][maxk - m - n][m];  
164                 }
165                 if(f[maxk - m - n][n][m] < ansnum){
166                     ans = m; ansnum =f[maxk - m - n][n][m];  
167                 }
168                }
169           if(ans) break;
170         }
171         printf("%d %d\n",ansnum,ans);
172     }
173 }
等一会看看别人的解题法，如何用最短路