刘汝佳说这是一道最短路，可是我怎么也想不出如何建图，把问题转换为最短路问题，我就想自己的办法。感觉这个题可以用三维dp；每一维代表一个瓶子 f[maxn][maxn][maxn]；状态转移我就想：每一次倒水一定要把一个倒完或把另一个装满才有意义，因为只有这样三个瓶的水量才知道；所以可以根据这个进行状态转移。状态转移代码有点啰嗦，主要是不同维不能统一一个式子。最后想到用队列来存变化的状态。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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 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 }
等一会看看别人的解题法，如何用最短路