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