【题目描述】
有三个没有刻度的水壶，容量分别为a，b和c（单位为升，都是<=200的正整数）。初始时前两个水壶是空的，而第三个装满了水。每次可以从一个水壶往一个水壶里倒水，直到一个水壶倒空或者另一个水壶倒满。为了让某个水壶恰好有d升水，至少要倒多少升的水？如果无解，找一个小于且最接近d的d’代替d。
【输入输出】
输入
第一行一个整数 t ，代表有 t 组测试数据，接下来 t 行每行包括 a, b, c, d 四个整数，分别代表三个水壶的容量 a, b, c 和目标水量 d 。
输出
输出共 t 行，每一行包括两个整数，分别是最少的倒水量和目标水量（d 或者 d′）。
【分析】
假设某一时刻，第一个杯子中有v₁升水，第二个杯子中有v₂升水，第三个杯子中有v₃升水，称此时的状态为(v₁, v₂, v₃)。我们可以把“状态”想成途中的一个结点，通过如何倒水就可以实现状态的转化，那么就可以构成一个状态图。不过提到了图，不代表一定就要建图，因为每一个状态的倒水方式都有最多6种（3² - 3，不能自己往自己倒），那么完全可以求最图上最短路时现算出每一个结点的出边，这种不建图却用到了图论的方法称为隐式图。然后跑最短路的话这里采用 spfa。
不过先来谈谈建图的方法。对于每一个结点，它的出边可以算出来，那么就可以用 bfs 来建图，然后存图的话就可以用 vector。值得注意的是，三个水壶中的水永远是不变的，恒等于第三个水壶的容量，所以可以用前两个水壶中的水表示第三个水壶中的水，建图就可以从三维降低到二维。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF = ;
const int maxn = ;
struct Cup //用结构体比较方便
{
int wa[];
};
int wmax[], d; //wmax三个杯子容量，d目标水量
bool exist[maxn][maxn]; //本来三维，可用二维表示,判断点是否存在
vector<Cup>v[maxn][maxn];//同理
vector<int>c[maxn][maxn];
int daoshui(int a, int b, int amax, int bmax, int& newa, int& newb) //a往b倒
{
if(a >= bmax - b) //b被灌满
{
newa = a - (bmax - b); newb = bmax; return bmax - b;
}
else //a被倒空
{
newa = ; newb = b + a; return a;
}
}
void init()
{
memset(exist, , sizeof(exist));
for (int i = ; i < maxn; i++)
for(int j = ; j < maxn; ++j)
{
v[i][j].clear(); c[i][j].clear();
}
return;
}
void build() //用bfs建图
{
init();
exist[][] = ;
queue<Cup>q; q.push((Cup){, , wmax[]});
while(!q.empty())
{
Cup now = q.front(); q.pop();
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
{
if(i == j) continue; //不能自己往自己倒
int t[]; Cup neww = now;
int cost = daoshui(now.wa[i], now.wa[j], wmax[i], wmax[j], t[i], t[j]);
neww.wa[i] = t[i]; neww.wa[j] = t[j];
if(!exist[neww.wa[]][neww.wa[]]) //要进入的这一个状态没被访问过
{
/*在强调一下，之所以开二维，是因为已知前两个杯子里的水，就可以
求第三个，所以像exist这样的数组，永远是exist[x.wa[0][x.wa[1]],
而不可能出现exist[x.wa[2]][x.wa[]]。我刚开始wa就是因为写成了
exist[neww.wa[i]][neww.wa[j]]*/
exist[neww.wa[]][neww.wa[]] = ;
v[now.wa[]][now.wa[]].push_back(neww);//从now这个状态添加一条出边
c[now.wa[]][now.wa[]].push_back(cost);
q.push(neww);
}
}
} }
int dis[maxn][maxn], vis[maxn][maxn];
void spfa()
{
for(int i = ; i < maxn; ++i)
for(int j = ; j < maxn; ++j)
{
dis[i][j] = INF; vis[i][j] = ;
}
queue<Cup>q; q.push((Cup){, , wmax[]}); //初始状态
dis[][] = ;
while(!q.empty())
{
Cup now = q.front(); q.pop();
vis[now.wa[]][now.wa[]] = ;
for(int i = ; i < v[now.wa[]][now.wa[]].size(); ++i)
{
Cup neww = v[now.wa[]][now.wa[]][i];
if(dis[now.wa[]][now.wa[]] + c[now.wa[]][now.wa[]][i] < dis[neww.wa[]][neww.wa[]])
{ // 有更好的结果就更新
dis[neww.wa[]][neww.wa[]] = dis[now.wa[]][now.wa[]] + c[now.wa[]][now.wa[]][i];
if(!vis[neww.wa[]][neww.wa[]])
{
vis[neww.wa[]][neww.wa[]] = ;
q.push(neww);
}
}
}
}
int ans1 = , ans2 = ;
for(int i = ; i < maxn; ++i)
for(int j = ; j < maxn; ++j)
{
if(exist[i][j]) //这个点存在
{
int newd = ;
if(i <= d && i >= newd) newd = i; //不断更新d′，使 d′不断趋近于 d。
if(j <= d && j >= newd) newd = j;
int cwa = wmax[] - i - j;
if(cwa <= d && cwa >= newd) newd = cwa;
if(newd > ans1 || (newd == ans1 && dis[i][j] < ans2))
{
ans1 = newd; ans2 = dis[i][j];
}
} }
printf("%d %d\n", ans2, ans1);
} int main()
{
int t; scanf("%d", &t);
while(t--)
{ scanf("%d%d%d%d", &wmax[], &wmax[], &wmax[], &d);
build();
spfa();
}
return ;
}
代码不短，不过要是改成隐式图搜索，建图的函数几乎就可以全省了。
那么怎么改呢？想一想建图只不过就是求出了 vector<Cup>v[maxn][maxn] 和 vector<Cup>c[maxn][maxn]，那么我们只要将 spfa中的 vector<Cup>v[maxn][maxn] 和 vector<Cup>c[maxn][maxn]替换成找出边和求边权的语句不就行了吗？
看看上面的代码，这个语句就是
int daoshui(int a, int b, int amax, int bmax, int& newa, int& newb)
{
if(a >= bmax - b)
{
newa = a - (bmax - b); newb = bmax; return bmax - b;
}
else
{
newa = ; newb = b + a; return a;
}
} for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
{
if(i == j) continue;
int t[]; Cup neww = now;
int cost = daoshui(now.wa[i], now.wa[j], wmax[i], wmax[j], t[i], t[j]);
}
那么就可以改了
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
const int INF = 0x3f3f3f3f;
struct Point
{
int w[];
};
int wmax[], d;
int pour(int a, int b, int amax, int bmax, int& na, int& nb){ // a -> b
if (bmax - b >= a) {na = , nb = b + a; return a;}
else {na = a - (bmax - b), nb = bmax; return bmax - b;}
}
int dist[maxn][maxn];
int vis[maxn][maxn];
void spfa(){
queue<Point>q; q.push((Point){, , wmax[]});
for (int i = ; i < maxn; i++)
for (int j = ; j < maxn; j++) dist[i][j] = INF;
dist[][] = ;
while (!q.empty()){
Point now = q.front(); q.pop(); vis[now.w[]][now.w[]] = ;
for (int i = ; i < ; i++){
for (int j = ; j < ; j++){
if (i == j) continue;
int t[];
Point np = now;
int cost = pour(np.w[i], np.w[j], wmax[i], wmax[j], t[i], t[j]);
np.w[i] = t[i], np.w[j] = t[j];
if (dist[np.w[]][np.w[]] > dist[now.w[]][now.w[]] + cost){
dist[np.w[]][np.w[]] = dist[now.w[]][now.w[]] + cost;
if (!vis[np.w[]][np.w[]]){
vis[np.w[]][np.w[]] = ;
q.push(np);
}
}
}
}
}
int ans1 = , ans2 = ;
for (int i = ; i < maxn; i++){
for (int j = ; j < maxn; j++){
if (dist[i][j] < INF){
int nd = ;
if (i <= d && i >= nd) nd = i;
if (j <= d && j >= nd) nd = j;
int k = wmax[] - i - j;
if (k <= d && k >= nd) nd = k;
if (nd > ans1 || (nd == ans1 && dist[i][j] < ans2)) {ans1 = nd; ans2 = dist[i][j];}
}
}
}
printf("%d %d\n", ans2, ans1);
}
int main()
{
int t; scanf("%d", &t);
while(t--)
{
scanf("%d%d%d%d", &wmax[], &wmax[], &wmax[], &d);
spfa();
}
return ;
}
代码量骤减。。