UVA 10603 Fill ( PFS )

UVa Online Judge
題目要求用最少的水來往達到 d或接近 d，又注意到水不會減少亦不會增加，故狀態只有二維 ( 知道其中兩個分別裝了多少就能知道剩下的那個 )，這是一種隱式圖走訪的問題，可以用 PFS解決。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200 + 10;

int botmx[3], ans[MAXN];
bool vis[MAXN][MAXN];

struct State{
    int bot[3], cost;
    bool operator < (const State &b)const {
        return cost > b.cost; //so that small will come out first
    }
};
void update_ans(const State &s){
    for(int i = 0; i < 3; ++i){
        int d = s.bot[i];
        if( ans[d] == -1 || s.cost < ans[d] ) ans[d] = s.cost;
    }
}
void solve(int a, int b, int c, int d){
    botmx[0] = a, botmx[1] = b, botmx[2] = c;
    memset( vis, false, sizeof(vis) );
    memset( ans, -1, sizeof(ans) );
    priority_queue<State> pq;
    
    State start;
    start.cost = 0, start.bot[0] = start.bot[1] = 0, start.bot[2] = c;
    pq.push( start );
    vis[ 0 ][ 0 ] = true; //bot a = 0, b = 0

    while( !pq.empty() ){
        State s = pq.top(); pq.pop();
        update_ans( s );
        if( ans[d] >= 0 ) break;

        for(int i = 0; i < 3; ++i) //pours from i to j
            for(int j = 0; j < 3; ++j) if( i != j ){
                if( s.bot[i] == 0 || s.bot[j] == botmx[j] ) continue;
                int delta = min( s.bot[i], botmx[j] - s.bot[j] );
                State s2; memcpy( &s2, &s, sizeof(s) );
                s2.cost = s.cost + delta;
                s2.bot[i] = s.bot[i] - delta;
                s2.bot[j] = s.bot[j] + delta;
                if( !vis[ s2.bot[0] ][ s2.bot[1] ] ){
                    vis[ s2.bot[0] ][ s2.bot[1] ] = true;
                    pq.push( s2 );
                }
            }
    }

    for(int i = d; i >= 0; --d) if( ans[d] >= 0 ){
        printf("%d %d\n", ans[d], d);
        return;
    }
}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
        solve(a, b, c, d);
    }
    return 0;
}