uva 10603

紫皮书的例题

照着敲了一遍，非原创

大题思路主要是三杯水，而水的总数是知道的，相当于知道第一第二杯水的体积，第三杯水的体积也就确定了。

用第一第二杯水的体积来标记数组是否遍历过

优先队列来找移动体积最少的

主要update_ans()函数进行每次判断

void update_ans(Node & u){

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

        int d = u.v[i];

        if(ans[d] <  || ans[d] > u.dist)

            ans[d] = u.dist;

    }

}

然后就是找第i杯水应该往第j杯水移动水的体积

符合条件进行入队操作

最后在ans数组寻找合适的解……！！！

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <stack>

#include <cctype>

#include <string>

#include <malloc.h>

#include <queue>

#include <map>

using namespace std;

const int INF = 0xffffff;

const double esp = 10e-;

const double Pi =  * atan(1.0);

const int Maxn = +;

const int mod = ;

const int dr[] = {,,-,,-,,-,};

const int dc[] = {,,,-,,-,-,};

struct Node{

    int v[];

    int dist;

    bool operator < (const Node & rhs)const{

        return dist > rhs.dist;

    }

};

int vis[Maxn][Maxn],cap[],ans[Maxn];

void update_ans(const Node & u){

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

        int d = u.v[i];

        if(ans[d] <  || u.dist < ans[d])

            ans[d] = u.dist;

    }

}

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

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

    memset(vis,,sizeof(vis));

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

    priority_queue<Node>q;

    Node start;

    start.dist = ;

    start.v[] = ;

    start.v[] = ;

    start.v[] = c;

    q.push(start);

    vis[][] = ;

    while(!q.empty()){

        Node u = q.top();

        q.pop();

        update_ans(u);

        if(ans[d] >= )

            break;

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

            for(int j = ;j < ;j++){

                if(i == j){

                    continue;

                }

                if(u.v[i] ==  || u.v[j] == cap[j])

                    continue;

                int amount = min(cap[j],u.v[i]+u.v[j]) - u.v[j];///计算将i倒入j的数量

                Node u2;

                memcpy(&u2,&u,sizeof(u));

                u2.dist = u.dist + amount;

                u2.v[i] -= amount;

                u2.v[j] += amount;

                if(!vis[u2.v[]][u2.v[]]){

                    vis[ u2.v[] ][u2.v[] ] = ;

                    q.push(u2);

                }

            }

        }

    }

    while(d >= ){

        if(ans[d] >= ){

            printf("%d %d\n",ans[d],d);

            return;

        }

        d--;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("inpt.txt","r",stdin);

#endif

    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);

    }

    return ;

}