题目链接： option=com_onlinejudge&Itemid=8&page=show_problem&problem=1544">click here~
此题我预计是加强过数据，在我纠结了非常久的时候我交了好几份网上的代码不是WA就是TLE。在我非常迷茫的时候我又交了一份，AC了(尽管我用随机数据找到了他代码一个不能过的数据)。
给了我信心。然后我拿他的代码用随机数跟我的代码进行測试。再用FC找不同。。发现了一个致命的错误。一般来说，BFS或者DFS都是须要有一个vis数组或者哈希来判重，可是此题判重是有非常大问题的，相同对于3个水杯的状态，在3步下或许流量是50，然后这个状态被标记，5步的时候又出现了这个状态（能够理解为还有一个分支），可是流量却是35，假设用个二维数组判重（没有必要用三维的，由于和是一样的，二维就能够了），那么这个状态的流量就不会更新。题目的意思却是说要用最小的流量去到达这个状态，无论是得到终于的目标还是比目标小近期目标的状态。
所以我感觉这题的标准解法应该不是 bfs，由于能够说是算暴力了。每一次的状态（假设流量比上一个到这个状态的流量少）都须要更新，不断更新直到最后。
在uva toolkit上此题的思路是dp或dijkstra。这2样还没怎么搞不太会。建图也想不到想法。感觉就算建了还是搜索的东西啊
尽管A了，可是感觉不爽啊。另外我找的那个A了的代码没过的数据是：33 12 113 6
他的结论是 174 6，我的结论是171 6，在uva toolkit上也是我的答案。可是我认为他的思路应该是正确的，没细看。。实在是太长了。
假设有想法的欢迎留言。
代码供參考：
#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define ll long long
#define NMAX 20000
typedef int state[3];
state st[NMAX],a;
int pour[NMAX];
int record[205];
int target;
int vis[205][205],vispour[205][205];
int try_to_insert(int x,int tpour)
{
state &k = st[x];
if(vis[k[0]][k[1]] != 1 || vispour[k[0]][k[1]] > tpour)
{
vis[k[0]][k[1]] = 1;
vispour[k[0]][k[1]] = tpour;
return 1;
}
return 0;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("o.txt","w",stdout);
int i,j,t,ans;
scanf("%d",&t);
while(t--)
{
memset(record,0,sizeof(record));
memset(vis,0,sizeof(vis));
memset(vispour,0,sizeof(vis));
scanf("%d%d%d%d",&a[0],&a[1],&a[2],&target);
st[1][0] = st[1][1] = 0;
st[1][2] = a[2];
memset(pour,0,sizeof(pour));
record[a[2]] = 1;
int front = 1,rear = 2;
vis[0][0] = 1;
bool flag = false;
while(front < rear)
{
for(i = 0; i < 3; i++)
if(record[st[front][i]] == 0 || pour[record[st[front][i]]] > pour[front])
record[st[front][i]] = front;
for(i = 0; i < 3; i++)
if(st[front][i] == target)
{
if(flag)
ans = pour[ans] > pour[front]?front:ans;
else
ans = front;
flag = true;
break;
}
for(i = 0; i < 3; i++)
{
state &w = st[front];
if(w[i] != 0)
{
for(j = 0; j < 3; j++)
{
if(i == j || (i != j && w[j] == a[j])) continue;
state &temp = st[rear];
memcpy(temp,w,sizeof(w));
int pp;
if(w[i] + w[j] > a[j])
{
pp = a[j] - w[j];
temp[i] = w[i] - pp;
temp[j] = a[j];
}
else
{
pp = w[i];
temp[i] = 0;
temp[j] = w[j] + pp;
}
int tpour;
tpour = pour[front] + pp;
if(try_to_insert(rear,tpour))
{
pour[rear] = tpour;
rear++;
}
}
}
}
front++;
}
if(record[target] == 0)
{
for(i = target; record[i] == 0; i--);
printf("%d %d\n",pour[record[i]],i);
}
else printf("%d %d\n",pour[ans],target);
}
return 0;
}