题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1495
非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16814 Accepted Submission(s): 6805
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3
4 1 3
0 0 0
4 1 3
0 0 0
Sample Output
NO
3
3
Author
seeyou
Source
题解：
1.由于每个容器不超过100， 所以枚举所有状态（1e6）也不会超时。所以直接用BFS。
2.判重：
2.1：其中S<=100, 1<=N<100, 1<=M<100，所以可以将当前三个容器的可乐量压缩成一个int类型，且最大不超过1009999（S放在前面，如果放在中间或者后面，就要加多一位了，这里有讲究），然后就可以开个vis[]数组直接检查状态status是否已经访问过了。
2.2：其实不用把三个容器压缩成一个int类型，可以直接开个三维数组vis[110][110][110]，每一维对应一个容器，也是1e6级别的大小，而且更加方便灵活。
2.3：其实开二维数组就够了，因为总的可乐量是确定的，当其中两个容器的可乐量确定了，那剩下的容器的可乐量也就确定了。这一个简单的优化又把内存消耗降低了100倍。
关于判重，目前自己有三个习惯的方法：STL的set、vis多维判重 与 vis status(int类型的以为判重) 。
1. set判重，适用状态高度离散的判重（开数组不能满足其范围）， 特点慢，能用数组判重就尽量不要用set判重。
2.vis多维判重， 适用于状态集中且维度较少的情况。
3.staus判重，适用于状态集中且维度较多的情况， 其本质就是把所有维度的状态都压缩成一个int类型， 所以status本质是一个哈希值。
2.1（status判重）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 2e6+; //0为容器S, 1为容器N， 2为容器M
struct node
{
int status, con[], step; //con[i]为容器i当前盛的可乐体积
};
int vol[], vis[MAXN]; //vol[i]为容器i的容量 queue<node>que;
int bfs()
{
ms(vis,);
while(!que.empty()) que.pop(); node now, tmp;
now.con[] = vol[]; //初始状态只用容器S盛有可乐
now.con[] = now.con[] = ;
now.status = vol[]*; //初始的状态
now.step = ;
vis[now.status] = ;
que.push(now); while(!que.empty())
{
now = que.front();
que.pop(); // cout<< now.status <<endl;
if((now.con[]==vol[]/ && now.con[]==vol[]/)
|| (now.con[]==vol[]/ && now.con[]==vol[]/)
|| (now.con[]==vol[]/ && now.con[]==vol[]/))
return now.step; for(int i = ; i<; i++) //模拟倒水的过程， i为倒， j为被倒
for(int j = ; j<; j++)
{
if(i==j) continue;
tmp = now;
int pour = min(tmp.con[i], vol[j]-tmp.con[j]); //能倒多少水
tmp.con[j] += pour;
tmp.con[i] -= pour;
tmp.status = tmp.con[]*+tmp.con[]*+tmp.con[]; //更新状态
if(!vis[tmp.status])
{
vis[tmp.status] = ;
tmp.step++;
que.push(tmp);
}
}
}
return -;
} int main()
{
while(scanf("%d%d%d",&vol[], &vol[], &vol[]) && (vol[]||vol[]||vol[]))
{
if(vol[]%) //奇数肯定不能平分
{
printf("NO\n");
continue;
}
int ans = bfs();
if(ans==-)
printf("NO\n");
else
printf("%d\n", ans);
}
return ;
}
2.2（三维判重）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = +; struct node
{
int con[], step;
};
int vol[], vis[MAXN][MAXN][MAXN]; queue<node>que;
int bfs()
{
ms(vis,);
while(!que.empty()) que.pop(); node now, tmp;
now.con[] = vol[];
now.con[] = now.con[] = ;
now.step = ;
vis[now.con[]][now.con[]][now.con[]] = ;
que.push(now); while(!que.empty())
{
now = que.front();
que.pop(); if((now.con[]==vol[]/ && now.con[]==vol[]/)
|| (now.con[]==vol[]/ && now.con[]==vol[]/)
|| (now.con[]==vol[]/ && now.con[]==vol[]/))
return now.step; for(int i = ; i<; i++) //模拟倒水的过程
for(int j = ; j<; j++)
{
if(i==j) continue;
tmp = now;
int pour = min(tmp.con[i], vol[j]-tmp.con[j]);
tmp.con[j] += pour;
tmp.con[i] -= pour;
if(!vis[tmp.con[]][tmp.con[]][tmp.con[]])
{
vis[tmp.con[]][tmp.con[]][tmp.con[]] = ;
tmp.step++;
que.push(tmp);
}
}
}
return -;
} int main()
{
while(scanf("%d%d%d",&vol[], &vol[], &vol[]) && (vol[]||vol[]||vol[]))
{
if(vol[]%)
{
printf("NO\n");
continue;
}
int ans = bfs();
if(ans==-)
printf("NO\n");
else
printf("%d\n", ans);
}
return ;
}
2.3（二维判重，推荐使用）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = +; struct node
{
int con[], step;
};
int vol[], vis[MAXN][MAXN]; queue<node>que;
int bfs()
{
ms(vis,);
while(!que.empty()) que.pop(); node now, tmp;
now.con[] = vol[];
now.con[] = now.con[] = ;
now.step = ;
vis[now.con[]][now.con[]] = ;
que.push(now); while(!que.empty())
{
now = que.front();
que.pop(); if((now.con[]==vol[]/ && now.con[]==vol[]/)
|| (now.con[]==vol[]/ && now.con[]==vol[]/)
|| (now.con[]==vol[]/ && now.con[]==vol[]/))
return now.step; for(int i = ; i<; i++) //模拟倒水的过程
for(int j = ; j<; j++)
{
if(i==j) continue;
tmp = now;
int pour = min(tmp.con[i], vol[j]-tmp.con[j]);
tmp.con[j] += pour;
tmp.con[i] -= pour;
if(!vis[tmp.con[]][tmp.con[]])
{
vis[tmp.con[]][tmp.con[]] = ;
tmp.step++;
que.push(tmp);
}
}
}
return -;
} int main()
{
while(scanf("%d%d%d",&vol[], &vol[], &vol[]) && (vol[]||vol[]||vol[]))
{
if(vol[]%)
{
printf("NO\n");
continue;
}
int ans = bfs();
if(ans==-)
printf("NO\n");
else
printf("%d\n", ans);
}
return ;
}