Traveling by Stagecoach POJ - 2686

状态压缩DP

题目描述：旅行商要从a城市到b城市，它共有n张马车票，一共有p条道路，m个城市，每两个城市之间花费的时间是道路之间的距离除以马车的数量，求最小的花费时间。

解题分析：关键还是在于怎么表示状态，定义dp[s][v]为票还剩s,现在在城市v所花费的最小时间。那答案就是min{ 0<k<s| dp[k][b]}.下面考虑状态转移方程，从v城市移动到u城市

花费车票i,对应的状态转移方程就是 dp[s^(1<<i)][u] = min(dp[s^(1<<i)][u] , dp[s][v] + graph[v][u] / tic[i] );

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <cstdlib>
#include <sstream>
#include <string>
#define error() cout << "#########" << endl
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double inf = 1e20;
const double esp = 1e-9;
const int dr[] = {0,1,0,-1},dc[] = {-1,0,1,0};


const int maxn = 30 + 5;
double dp[1<<10][maxn];//dp[s][v]现在在城市v，还有票s所花费的最小时间
double graph[maxn][maxn];
double tic[maxn];
int n,m,p,st,ed;

void init()
{
    for(int i = 0; i <= m; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            graph[i][j] = INF;
        }
    }
    for(int s = 0; s < 1<<n; s++)
    {
        for(int i = 0; i <= m; i++)
        {
            dp[s][i] = INF;
        }
    }
}

void solve()
{
    double res = INF;
    for(int s = (1<<n) -1; s >= 0; s--) dp[s][st] = 0;
    for(int s = (1<<n) -1; s >= 0; s--)//顺序是逆序的,这个顺序很重要.
    {
        res  = min(res,dp[s][ed]);
        for(int v = 1; v <= m; v++)
        {
            for(int u = 1;u <= m; u++)
            {
                if(graph[v][u] != INF)
                {
                    for(int i = 0; i < n; i++)
                    {
                        if(s&(1<<i))
                        {
                            dp[s^(1<<i)][u]  = min(dp[s^(1<<i)][u],dp[s][v] + graph[v][u] / tic[i]);
                        }
                    }
                }
            }
        }
    }
    if(res == INF) printf("Impossible\n");
    else
    {
        printf("%.3f\n",res);
    }
}

int main()
{
    while(cin >> n >> m >> p >> st >> ed&&(n||m||p||st||ed))
    {
        init();
        for(int i = 0; i < n; i++)
        {
            cin >> tic[i];
        }
        for(int i = 0; i < p; i++)
        {
            int u,v;
            double w;
            scanf("%d %d %lf",&u,&v,&w);
            graph[u][v] = graph[v][u] = w;
        }
        solve();
    }
    return 0;
}

第一次做状态压缩DP的问题，自己想还是没想出来，还是看的白书的解析。在写上面的代码的时候思考了一个问题什么时候循环是顺序的，什么时候是逆序的。在这个题中我想是根据状态转移方程决定的，状态转移方程的右边s表示的集合要大于左边s表示的集合，左边的状态是由右边的转移过来的，所以应该优先求出右边的状态的结果，而右边的s表示的集合更大，所以最外层的循环要逆序。

下面根据上面的代码写了个记忆化搜索的版本,其实是一样的。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const double INF = 1000000000;
const int maxn = 30 + 5;
double graph[maxn][maxn];
int tic[maxn];
double dp[1<<10][maxn];//dp[s][v]票还剩s,现在在城市v所花费的最小时间
int n,m,p,st,ed;

double dfs(int s,int v)
{
    if(dp[s][v] != -1) return dp[s][v];
    else if(v == st) return dp[s][v] = 0;
    else
    {
        double res = INF;
        for(int u = 1; u <= m; u++)
        {
            if(graph[u][v] != INF)
            {
                for(int i = 0; i < n; i++)
                {
                    if(!(s&(1<<i)))
                    {
                       res = min(res,dfs(s|(1<<i),u) + graph[u][v] / tic[i]);
                    }
                }
            }
        }
        return dp[s][v] = res;
    }

}

void init()
{
    for(int i = 0; i <= m; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            graph[i][j] = INF;
        }
    }
    for(int i = 0; i < 1<<n; i++)
    {
        for(int k = 0; k <= m; k++)
        {
             dp[i][k] = -1;
        }
    }
}

int main()
{
    while(cin >> n >> m >> p >> st >> ed && (n||m||p||st||ed))
    {
        init();
        for(int i = 0; i < n; i++)
        {
            cin >> tic[i];
        }
        for(int  i = 0; i < p; i++)
        {
            int u,v;
            double w;
            scanf("%d %d %lf",&u,&v,&w);
            graph[u][v] = graph[v][u] = w;
        }
        double res = INF;
        for(int s = (1<<n) - 1; s >= 0; s--)
        {
            res = min(res,dfs(s,ed));
        }
        if(res == INF)
        {
            printf("Impossible\n");
        }
        else
        {
            printf("%.3f\n",res);
        }
    }
    return 0;
}