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