hdu 3339 In Action

クリックしてリンクhdu 3339を開く
考え方:最短+floyd+0/1リュックサック分析:1この問題は制限条件のエネルギーを多くして、つまりすべての点に自分のエネルギー値があります.2問題はエネルギーが少なくとも1/2より大きいことを要求する場合の最短ルートで、最初は貪欲だと理解して、それから絶え間ないWAで、それからdpだと知った.実はよく理解して、すべての点のエネルギーに対して2つの選択だけが取るか取らないかで、それではこれは典型的な0/1リュックサックの問題です.しかし、リュックサックの容量として何を選ぶかという問題があり、最初はpowを選びました.sumはリュックサックの容量として、それから距離は価値のためにdpを求めて、それからまたWAです.その後costでsumはリュックサックの容量として,powを価値としてdpを解き,最後にdp[i]>sum/2があるかどうかを判断して1 Aとした.3注意問題は複数の戦車があることを明確に指摘しており、各戦車が0から出て1つの点しか攻撃できないという意味だ.コード:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF

int t , n , m;
long long ans;
long long cost_sum , pow_sum;
long long dis[MAXN][MAXN];
long long dp[600010];
long cost[MAXN];
int pow[MAXN];

/*   */
void init(){
   int i , j;
   for(i = 0 ; i <= n ; i++){
      for(j = 0 ; j <= n ; j++)
          dis[i][j] = INF;
      dis[i][i] = 0;
   }
}

/*floyd     */
void floyd(){
   int i , j , k;
   for(k = 0 ; k <= n ; k++){
      for(i = 0 ; i <= n ; i++){
         for(j = 0 ; j <= n ; j++){
            if(dis[i][j] > dis[i][k]+dis[k][j])
              dis[i][j] = dis[i][k]+dis[k][j];
         }
      }
   }
}

long long max(long long a , long long b){
   return a > b ? a : b;
}

/*DP  */
void DP(){
   memset(dp , 0 , sizeof(dp));
   for(int i = 1 ; i <= n ; i++){
      if(cost[i] == INF)/*  cost[i] = INF     ，        */
        continue;
      for(int j = cost_sum ; j >= cost[i] ; j--)
         dp[j] = max(dp[j-cost[i]]+pow[i] , dp[j]);
   }
}

int main(){
   int a , b , v , flag;
   scanf("%d" , &t);
   while(t--){
      scanf("%d%d" , &n , &m);
      init();
      for(int i = 0 ; i < m ; i++){
         scanf("%d%d%d" , &a , &b , &v);
         if(dis[a][b] > v)/*  */
           dis[a][b] = dis[b][a] = v;
      }

      pow_sum = cost_sum = 0;
      for(int i = 1 ; i <= n ; i++){
         scanf("%d" , &pow[i]);
         pow_sum += pow[i];
      }

      floyd();
      for(int i = 1 ; i <= n ; i++){
         cost[i] = dis[0][i];/*  0-       */
         if(cost[i] != INF)/*  0          */
            cost_sum += cost[i];
      }
      
      DP();
      flag = 0;
      for(long long i = 1 ; i <= cost_sum ; i++){
         if(dp[i] > pow_sum/2){
            flag = 1;
            ans = i;
            break;
         }
      }
      if(!flag)
        printf("impossible
");
      else
        printf("%lld
" , ans);
   }
   return 0;
}