首页 > 代码库 > 10603 Fill (BFS)
10603 Fill (BFS)
题目大意:有三个杯子,容量分别为a,b,c,一开始,a,b都是空的,只有c是满的,现在开始倒水,一次倒水结束的条件是倒水的杯子倒完或者被倒的杯子倒满,问要使得至少一个杯子有恰好d单位的水,最少的倒水量,如果d不可能,那么就输出最大的小于d的数dd,和最小倒水量
解题思路:只有三个杯子,用bfs搜索达到d的最少水量,状态得开二维,不然会超时。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define inf 0x3f3f3f3f using namespace std; struct jug{ int L[3],s; friend bool operator<(jug a,jug b){ return a.s>b.s; } }; int a,b,c,d; int vis[210][210]; int S[3],cap[3],TS[3]; int mark; int bfs(int d){ queue<jug> q; jug f; f.L[0]=0,f.L[1]=0,f.L[2]=c,f.s=0; q.push(f); vis[0][0]=1; int ret=inf; while(!q.empty()){ jug x=q.front(); q.pop(); if(x.L[0]==d||x.L[1]==d||x.L[2]==d){ if(x.s<ret) ret=x.s; continue; } if(x.s>=ret) continue; for(int i=0;i<3;i++){ if(!x.L[i]) continue; for(int j=0;j<3;j++){ if(i==j) continue; if(x.L[j]==cap[j]) continue; jug tmp=x; if(x.L[i]+x.L[j]>cap[j]){ tmp.L[i]=x.L[i]+x.L[j]-cap[j]; tmp.L[j]=cap[j]; tmp.s+=cap[j]-x.L[j]; }else{ tmp.L[i]=0; tmp.L[j]=x.L[i]+x.L[j]; tmp.s+=x.L[i]; } if(vis[tmp.L[0]][tmp.L[1]]!=mark){ vis[tmp.L[0]][tmp.L[1]]=mark; q.push(tmp); } } } } mark++; return ret; } void solve(){ cap[0]=a,cap[1]=b,cap[2]=c; if(d>max(max(a,b),c)) {printf("0 0\n");return;} memset(vis,-1,sizeof vis); mark=0; int ret=bfs(d); if(ret!=inf) printf("%d %d\n",ret,d); else{ for(int i=d-1;i>=0;i--){ ret=bfs(i); if(ret!=inf){ printf("%d %d\n",ret,i); break; } } } } int main(){ int T; scanf("%d",&T); for(int ca=1;ca<=T;ca++){ scanf("%d%d%d%d",&a,&b,&c,&d); solve(); } return 0; }
10603 Fill (BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。