首页 > 代码库 > HDU 4284Travel（状压DP）

HDU 4284Travel（状压DP）

2024-07-15 13:09:21   230人阅读

HDU 4284    Travel

有N个城市，M条边和H个这个人（PP）必须要去的城市，在每个城市里他都必须要“打工”，打工需要花费Di，可以挣到Ci，每条边有一个花费，现在求PP可不可以从起点1走完所有的他必须要去的城市，打完所有的工，并且成功回到起点1

由于H<=15，所以显然可以状压，预处理这些都必须去的城市之间的最短距离（可以floyd），然后状压DP[S][i]表示他到达了S这些城市后正处在第i个城市里（所以S & (1<<i) != 0）的剩余的最大的钱的数量，然后状态转移就好了

上面求最短路直接用的floyd不会错貌似是因为数据里没有Ci<Di的数据，因为如果存在这种情况的话，虽然不考虑点的花费最短路是可以到的但是实际确实到不了的，导致不能走完所有的H个城市：

1
3 3 5
1 2 1
2 3 1
1 3 10
3
1 8 5
2 2 10
3 20 5

比如这样的数据应该输出NO但答案是YES（被这种自己出的数据坑了好久啊有木有！！！）

  1 //#pragma comment(linker,"/STACK:102400000,102400000")  2 #include <map>  3 #include <set>  4 #include <stack>  5 #include <queue>  6 #include <cmath>  7 #include <ctime>  8 #include <vector>  9 #include <cstdio> 10 #include <cctype> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 #define INF 1e8 17 #define inf (-((LL)1<<40)) 18 #define lson k<<1, L, mid 19 #define rson k<<1|1, mid+1, R 20 #define mem0(a) memset(a,0,sizeof(a)) 21 #define mem1(a) memset(a,-1,sizeof(a)) 22 #define mem(a, b) memset(a, b, sizeof(a)) 23 #define FOPENIN(IN) freopen(IN, "r", stdin) 24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    } 31  32 //typedef __int64 LL; 33 //typedef long long LL; 34 const int MAXN = 600; 35 const int MAXM = 100005; 36 const double eps = 1e-13; 37 //const LL MOD = 1000000007; 38  39 int T, N, M, H, Money; 40 int dis[MAXN][MAXN], add[MAXN], cost[MAXN]; 41 int citys[20], dp[1<<18][18]; 42  43 void init() 44 { 45     int u, v, w, c, a; 46      mem0(add); mem0(cost);mem1(dp); 47     scanf("%d %d %d", &N, &M, &Money); 48     for(int i =0 ; i <= N ;i ++ ) 49     { 50         dis[i][i] = 0; 51         for(int j = 0; j <= N ; j ++ ) 52             if(i != j) dis[i][j] = INF; 53     } 54     for(int i = 0; i < M; i ++ ) 55     { 56         scanf("%d %d %d", &u, &v, &w); 57         dis[u][v] = dis[v][u] = MIN(dis[u][v], w); 58     } 59     scanf("%d", &H); 60     for(int i = 1; i <= H; i ++ ) 61     { 62         scanf("%d %d %d", &u, &a, &c); 63         citys[i] = u; 64         add[i] = a; 65         cost[i] = c; 66     } 67 } 68  69 void floyd() 70 { 71     for(int k=1;k<=N;k++) 72     for(int i=1;i<=N;i++) 73     for(int j=1;j<=N;j++) 74     { 75         dis[i][j] = MIN(dis[i][j], dis[i][k] + dis[k][j]); 76     } 77 } 78  79 int main() 80 { 81     //FOPENIN("in.txt"); 82     while(~scanf("%d", &T)) while(T--) 83     { 84         init(); 85         floyd(); 86         int ans = -INF; H += 1; 87         citys[0] = 1; cost[0] = add[0] = 0; 88         dp[1][0] = Money; 89         for(int now = 1; now < (1<<H); now ++ ) 90         { 91             for(int u = 0; u < H; u ++ ) if(dp[now][u] != -1) 92             { 93                 for(int v = 1; v < H; v ++ ) if( (now & (1<<v)) == 0 ) 94                 { 95                     int next = now | (1<<v); 96                     if(dp[now][u] >= dis[citys[u]][citys[v]] + cost[v] ) 97                     { 98                         dp[next][v] = MAX(dp[now | (1<<v)][v], dp[now][u] - dis[citys[u]][citys[v]] - cost[v] + add[v]); 99                     }100                     if(next == (1<<H) - 1)101                     {102                         ans = MAX(ans, dp[next][v]);103                     }104                 }105             }106         }107        //printf("%d\n", ans);108         printf("%s\n", ans >= 0 ? "YES" : "NO");109     }110     return 0;111 }

 


联系
我们