HDU 4284Travel（状压DP）

有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（被这种自己出的数据坑了好久啊有木有！！！）

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e8

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int T, N, M, H, Money;

 int dis[MAXN][MAXN], add[MAXN], cost[MAXN];

 int citys[], dp[<<][];

 void init()

 {

     int u, v, w, c, a;

      mem0(add); mem0(cost);mem1(dp);

     scanf("%d %d %d", &N, &M, &Money);

     for(int i = ; i <= N ;i ++ )

     {

         dis[i][i] = ;

         for(int j = ; j <= N ; j ++ )

             if(i != j) dis[i][j] = INF;

     }

     for(int i = ; i < M; i ++ )

     {

         scanf("%d %d %d", &u, &v, &w);

         dis[u][v] = dis[v][u] = MIN(dis[u][v], w);

     }

     scanf("%d", &H);

     for(int i = ; i <= H; i ++ )

     {

         scanf("%d %d %d", &u, &a, &c);

         citys[i] = u;

         add[i] = a;

         cost[i] = c;

     }

 }

 void floyd()

 {

     for(int k=;k<=N;k++)

     for(int i=;i<=N;i++)

     for(int j=;j<=N;j++)

     {

         dis[i][j] = MIN(dis[i][j], dis[i][k] + dis[k][j]);

     }

 }

 int main()

 {

     //FOPENIN("in.txt");

     while(~scanf("%d", &T)) while(T--)

     {

         init();

         floyd();

         int ans = -INF; H += ;

         citys[] = ; cost[] = add[] = ;

         dp[][] = Money;

         for(int now = ; now < (<<H); now ++ )

         {

             for(int u = ; u < H; u ++ ) if(dp[now][u] != -)

             {

                 for(int v = ; v < H; v ++ ) if( (now & (<<v)) ==  )

                 {

                     int next = now | (<<v);

                     if(dp[now][u] >= dis[citys[u]][citys[v]] + cost[v] )

                     {

                         dp[next][v] = MAX(dp[now | (<<v)][v], dp[now][u] - dis[citys[u]][citys[v]] - cost[v] + add[v]);

                     }

                     if(next == (<<H) - )

                     {

                         ans = MAX(ans, dp[next][v]);

                     }

                 }

             }

         }

        //printf("%d\n", ans);

         printf("%s\n", ans >=  ? "YES" : "NO");

     }

     return ;

 }

巴特西

HDU 4284Travel（状压DP）

最新文章

热门文章