例题7-8 Fill倒水问题

Posted on | In |

题意：三个杯子容量分别为a，b，c，现在c是满的，a和b是空的，两个杯子 i 向 j 倒水，要么 i 倒完了 j 还没满，要么 j 满了 i 还有剩余，问达到某个杯子水量为d时总共倒得最小水量是多少？如果不能达到d，找一个小于d并且离d最近的一个解。

思路：倒水问题，但题目要求的是总的到水量，所以在bfs时到达过的状态还要检查更新，可能当前我确实到达d了用了sum水量，但可能后面还有比sum更小的解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream> 
#include<cstring>
#include<queue>
using namespace std;
int ans[1000];
int vis[100][100];
struct Node{
	int v[3];
	int dis;
	bool operator < (const Node& nhs)const{
		return dis>nhs.dis;
	}
};
void update(const Node &u){
	for(int i=0;i<3;i++){
		int volume=u.v[i];
		if(ans[volume]<0||ans[volume]>u.dis)
		ans[volume]=u.dis;}
	
}
void solve(int a,int b,int c,int d){
	memset(ans,-1,sizeof(ans));//!!!
	memset(vis,0,sizeof(ans));//!!!
	priority_queue<Node> queue;
	int cap[3];
	cap[0]=a;
	cap[1]=b;
	cap[2]=c;
	Node start;
	start.v[0]=0;
	start.v[1]=0;
	start.v[2]=c;
	start.dis=0;
	vis[0][0]=1;//!!
	queue.push(start);
	while(!queue.empty())	{
		Node u=queue.top();
		queue.pop();
		update(u);
		if(ans[d]>=0) break;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(i!=j){
					if(u.v[i]==0||u.v[j]==cap[j]) continue;
					int dis=min(u.v[i]+u.v[j],cap[j])-u.v[j];
					Node u2;
					memcpy(&u2,&u,sizeof(u));
					u2.v[i]-=dis;
					u2.v[j]+=dis;
					u2.dis=u.dis+dis;
					if(!vis[u2.v[0]][u2.v[1]]){
						vis[u2.v[0]][u2.v[1]]=1;
						queue.push(u2);
					}
					
				}
				
			} 
			
			
		}

	}
			while(d>=0){
			if(ans[d]>=0) {
				cout<<ans[d]<<" "<<d<<endl;
				break;
			}
			d--;
		}
}
int main(){
	int n,a,b,c,d;
	//freopen("t.txt","r",stdin);
	cin>>n;
	while(n--){
		cin>>a>>b>>c>>d;
		solve(a,b,c,d);
	}
	
	
}