本文共 2080 字，大约阅读时间需要 6 分钟。
紫皮书的例题
照着敲了一遍，非原创
大题思路主要是三杯水，而水的总数是知道的，相当于知道第一第二杯水的体积，第三杯水的体积也就确定了。
用第一第二杯水的体积来标记数组是否遍历过
优先队列来找移动体积最少的
主要update_ans()函数进行每次判断
void update_ans(Node & u){ for(int i = 0;i < 3;i++){ int d = u.v[i]; if(ans[d] < 0 || ans[d] > u.dist) ans[d] = u.dist; }}
然后就是找第i杯水应该往第j杯水移动水的体积
符合条件进行入队操作
最后在ans数组寻找合适的解……！！！
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int INF = 0xffffff;const double esp = 10e-8;const double Pi = 4 * atan(1.0);const int Maxn = 200+5;const int mod = 10000007;const int dr[] = { 1,0,-1,0,-1,1,-1,1};const int dc[] = { 0,1,0,-1,1,-1,-1,1};struct Node{ int v[3]; int dist; bool operator < (const Node & rhs)const{ return dist > rhs.dist; }};int vis[Maxn][Maxn],cap[3],ans[Maxn];void update_ans(const Node & u){ for(int i = 0;i < 3;i++){ int d = u.v[i]; if(ans[d] < 0 || u.dist < ans[d]) ans[d] = u.dist; }}void solve(int a,int b,int c,int d){ cap[0] = a,cap[1] = b,cap[2] = c; memset(vis,0,sizeof(vis)); memset(ans,-1,sizeof(ans)); priority_queue q; 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(); update_ans(u); if(ans[d] >= 0) break; for(int i = 0;i < 3;i++){ for(int j = 0;j < 3;j++){ if(i == j){ continue; } if(u.v[i] == 0 || u.v[j] == cap[j]) continue; int amount = min(cap[j],u.v[i]+u.v[j]) - u.v[j];///计算将i倒入j的数量 Node u2; memcpy(&u2,&u,sizeof(u)); u2.dist = u.dist + amount; 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(){#ifndef ONLINE_JUDGE freopen("inpt.txt","r",stdin);#endif int T,a,b,c,d; scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&a,&b,&c,&d); solve(a,b,c,d); } return 0;}
转载于:https://www.cnblogs.com/hanbinggan/p/4291541.html
