uva 10683 Fill

题意：

倒水问题，输出最少的倒水量和目标水量

如果无解，目标水量就是尽可能接近给定点的目标水量，但不得大于给定的目标水量

推推公式，不用分类讨论~\(≧▽≦)/~啦啦啦

#include<cstdio>

#include<cstring>

#include<queue>

#define N 201

using namespace std;

struct node

{

    int v[],dis;

    bool  operator < (node p) const

    {

        return dis>p.dis;

    }

}now,nxt;

int v[N][N],cap[],ans[N];

void up()

{

    int d;

    for(int i=;i<;i++)

    {

        d=now.v[i];

        if(ans[d]< || now.dis<ans[d]) ans[d]=now.dis;

    }

}

void solve(int a,int b,int c,int d)

{

    cap[]=a; cap[]=b; cap[]=c;

    memset(v,,sizeof(v));

    memset(ans,-,sizeof(ans));

    priority_queue<node>q;

    node s;

    s.dis=; s.v[]=; s.v[]=; s.v[]=c;

    q.push(s);

    v[][]=;

    while(!q.empty())

    {

        now=q.top(); q.pop();

        up();

        if(ans[d]>=) break;

        for(int i=;i<;i++)

         for(int j=;j<;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[]][nxt.v[]]) { v[nxt.v[]][nxt.v[]]=true; q.push(nxt); }

          }

    }

    while(d>=)

    {

        if(ans[d]>=) { printf("%d %d\n",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);

    }

}