題意給出3個(gè)杯子，只有最后一個(gè)杯子裝滿水，問(wèn)至少倒多少水才能使其中一個(gè)杯子里的水達(dá)到d升。

分析：這題關(guān)鍵在于優(yōu)先級(jí)隊(duì)列，每次都要取倒水量最小的狀態(tài)出來(lái)。

#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include<iostream> #include<queue> using namespace std; struct Node {int v[3], dist;bool operator<(const Node& u) const{return dist > u.dist;} }; const int maxn = 200 + 5; int vis[maxn][maxn], cap[3], ans[maxn]; void bfs(int a, int b, int c, int d) {priority_queue<Node>q;//優(yōu)先級(jí)隊(duì)列memset(vis, 0, sizeof(vis));memset(ans, -1, sizeof(ans));cap[0] = a, cap[1] = b, cap[2] = c;Node start;start.dist = 0;start.v[0] = 0; start.v[1] = 0; start.v[2] = c;q.push(start);vis[0][0] = 1;while (!q.empty()) {Node u = q.top(); q.pop();for (int i = 0; i < 3; i++) {int d = u.v[i];if (ans[d]<0 || ans[d]>u.dist)ans[d] = u.dist;//更新每個(gè)杯子水的狀態(tài)信息}if (ans[d] >= 0)break;//有目標(biāo)狀態(tài)信息，退出for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (u.v[i] == 0 || u.v[j] == cap[j])continue;//杯子滿了或者空了int amount = min(cap[j], u.v[j] + u.v[i]) - u.v[j];//加水量最小Node u2;memcpy(&u2, &u, sizeof(u));u2.dist = u.dist + amount;//u2的倒水量u2.v[i] -= amount;u2.v[j] += amount;if (!vis[u2.v[0]][u2.v[1]]) {vis[u2.v[0]][u2.v[1]] = 1;q.push(u2);}}}}while (d >= 0) {if (ans[d] >= 0) {printf("%d %d\n",ans[d], d);return;}d--;} } int main() {int kase,a,b,c,d;cin >> kase;while (kase-- > 0) {cin >> a >> b >> c >> d;bfs(a, b, c, d);}//system("pause");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的UVA10603 倒水问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。