https://vjudge.net/problem/UVA-10603
题意：
倒水问题，输出最少的倒水量和目标水量
如果无解，目标水量就是尽可能接近给定点的目标水量，但不得大于给定的目标水量
推推公式，不用分类讨论~(≧▽≦)/~啦啦啦
#include<cstdio> #include<cstring> #include<queue> #define N 201 using namespace std; struct node { int v[3],dis; bool operator < (node p) const { return dis>p.dis; } }now,nxt; int v[N][N],cap[3],ans[N]; void up() { int d; for(int i=0;i<3;i++) { d=now.v[i]; if(ans[d]<0 || now.dis<ans[d]) ans[d]=now.dis; } } void solve(int a,int b,int c,int d) { cap[0]=a; cap[1]=b; cap[2]=c; memset(v,0,sizeof(v)); memset(ans,-1,sizeof(ans)); priority_queue<node>q; node s; s.dis=0; s.v[0]=0; s.v[1]=0; s.v[2]=c; q.push(s); v[0][0]=1; while(!q.empty()) { now=q.top(); q.pop(); up(); if(ans[d]>=0) break; for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(i!=j) { if(!now.v[i] || now.v[j]==cap[j]) continue;// int amount=min(cap[j],now.v[i]+now.v[j])-now.v[j]; nxt=now; nxt.dis+=amount; nxt.v[i]-=amount; nxt.v[j]+=amount; if(!v[nxt.v[0]][nxt.v[1]]) { v[nxt.v[0]][nxt.v[1]]=true; q.push(nxt); } } } while(d>=0) { if(ans[d]>=0) { printf("%d %d ",ans[d],d); return;} d--; } } int main() { int T,a,b,c,d; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&a,&b,&c,&d); solve(a,b,c,d); } }