首页 > 代码库 > UVa10603 Fill （隐式图搜索+Dijkstra）
UVa10603 Fill （隐式图搜索+Dijkstra）
链接：http://acm.hust.edu.cn/vjudge/problem/19527
分析：隐式图搜索，从初始状态(0,0,c)开始，维护一个到达k升水所需的最少倒水量ans。结点状态设计为v[3]表示当前状态三个杯子中的水量和到达此状态的倒水量。用一个二维vis判重，因为只要第1,2个杯子里的水量确定第3个杯子里的水量也就确定了，所以二维就足以表示了。然后跑一边Dijkstra，用优先队列每次取出倒水量最少的的结点进行扩展，然后用到了一个定序的技巧，规定从i号杯子倒到j号杯子里，生成一个新的结点，维护v和dist，判重后加入队列中。最后打印输出d或d‘。
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 struct Node { 8 int v[3], dist; 9 bool operator < (const Node& rhs) const {10 return dist > rhs.dist;11 }12 };13 14 int const maxn = 200 + 5;15 int a, b, c, d, cap[3], vis[maxn][maxn], ans[maxn];16 17 void update_ans(const Node& u) {18 for (int i = 0; i < 3; i++) {19 int d = u.v[i];20 if (ans[d] < 0 || u.dist < ans[d]) ans[d] = u.dist;21 }22 }23 24 void solve() {25 cap[0] = a; cap[1] = b; cap[2] = c;26 memset(vis, 0, sizeof(vis));27 memset(ans, -1, sizeof(ans));28 priority_queue<Node> q;29 30 Node start;31 start.dist = 0;32 start.v[0] = 0; start.v[1] = 0; start.v[2] = c;33 vis[0][0] = 1;34 q.push(start);35 36 while (!q.empty()) {37 Node u = q.top(); q.pop();38 update_ans(u);39 if (ans[d] >= 0) break;40 for (int i = 0; i < 3; i++)41 for (int j = 0; j < 3; j++) if (i != j) {42 if (u.v[i] == 0 || u.v[j] == cap[j]) continue;43 int amount = min(cap[j], u.v[i] + u.v[j]) - u.v[j];44 Node u2;45 memcpy(&u2, &u, sizeof(u));46 u2.dist = u.dist + amount;47 u2.v[i] -= amount;48 u2.v[j] += amount;49 if (!vis[u2.v[0]][u2.v[1]]) {50 vis[u2.v[0]][u2.v[1]] = 1;51 q.push(u2);52 }53 }54 }55 while (d >= 0) {56 if (ans[d] >= 0) {57 printf("%d %d\n", ans[d], d);58 return;59 }60 d--;61 }62 }63 64 int main() {65 int T;66 scanf("%d", &T);67 while (T--) {68 scanf("%d%d%d%d", &a, &b, &c, &d);69 solve();70 }71 return 0;72 }
UVa10603 Fill （隐式图搜索+Dijkstra）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。