题目：
Sample Input
2
2 3 4 2
96 97 199 62
Sample Output
2 2
9859 62
题意：
有三个杯子它们的容量分别是a,b,c, 并且初始状态下第一个和第二个是空的， 第三个杯子是满水的。可以把一个杯子的水倒入另一个杯子，当然，当被倒的杯子满了或者倒的杯子水完了，就不能继续倒了。
你的任务是写一个程序计算出用最少的倒水量，使得其中一个杯子里有d升水。如果不能倒出d升水的话，那么找到一个d’ < d ，使得d’ 最接近d。
分析：
可以把每个状态即3个水杯里的水的数量的状态看成一个点，两个状态之间的转换关系（即A状态转移k升水后变成B状态）建边，边权为转移的水的升数。然后用spfa求最短路。最后从d开始for到0，看一下那一个状态是可以到达的，然后输出即可。对于d>c的情况，直接输出0 c就可以了（因为无论如何杯子里最多只会有c升水，而且一开始的时候根本不用转移水就可以了）。因为数据范围是<=200，水的总和一定，所以只要知道前两个杯子的状态就能推出第三个杯子的状态，所以总点数会小于200*200（有些状态是不会出现的）。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#include<queue>
#define INF 0xfffffff
#define Maxn 210 struct node
{
int x,y,c,next;
}t[Maxn*Maxn*];int len; bool inq[Maxn*Maxn]; int first[Maxn*Maxn],dis[Maxn*Maxn]; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y,int c)
{
if(x==y) return;
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
} queue<int > q; void spfa(int s)
{
memset(inq,,sizeof(inq));
memset(dis,,sizeof(dis));
while(!q.empty()) q.pop();
inq[s]=;dis[s]=;q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();inq[x]=;
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
if(!inq[y])
{
q.push(y);
inq[y]=;
}
}
}
}
} int ffind(int x,int c,int C)
{
int mn=INF;
for(int i=;i<=c-x;i++)
{
mn=mymin(mn,dis[i*C+c-x-i]);//-,-,d
mn=mymin(mn,dis[(c-x-i)*C+i]);//-,-,d
mn=mymin(mn,dis[x*C+c-x-i]);//d,-,-
mn=mymin(mn,dis[x*C+i]);//d,-,-
mn=mymin(mn,dis[i*C+x]);//-,d,-
mn=mymin(mn,dis[(c-x-i)*C+x]);//-,d,-
}
return mn;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(d>=c) {printf("0 %d\n",c);continue;}
len=;
memset(first,,sizeof(first));
int C=c+;
for(int i=;i<=c;i++)
for(int j=;i+j<=c;j++)
{
int k=c-i-j,st=i*C+j;
if(i<=b-j) ins(st,i+j,i);else ins(st,(i-b+j)*C+b,b-j);//1->2
if(i<=c-k) ins(st,j,i);else ins(st,(i-c+k)*C+j,c-k);//1->3
if(j<=a-i) ins(st,(i+j)*C,j);else ins(st,a*C+j-a+i,a-i);//2->1
if(j<=c-k) ins(st,i*C,j);else ins(st,i*C+j-c+k,c-k);//2->3
if(k<=a-i) ins(st,(i+k)*C+j,k);else ins(st,a*C+j,a-i);//3->1
if(k<=b-j) ins(st,i*C+j+k,k);else ins(st,i*C+b,b-j);//3->2
}
spfa();
for(int i=d;i>=;i--)
{
int x=ffind(i,c,C);
if(x<INF) {printf("%d %d\n",x,i);break;}
}
}
return ;
}
[UVA10603]
2016-04-09 10:13:24
