HDU 3339 In Action 解題報告（最短路+背包）

晚上看圖論500的時候看到一個最短路+背包的題，有點感興趣，於是花了一個多小時A了這題。

題目大意：恐怖分子欲炸地球，引爆核彈需要用一半的電。而電分布在不同的電站。每個電站都存有不同的電。目的是派出坦克，毀壞電站，使其無法引爆。
給出無向圖，要求以最小總距離，毀壞一半以上的電。 注意每個電站都需要一個坦克。

每個電站都有自己的花費（0到它的最短路），以及價值（電量）。於是轉化為最少的花費去點一半以上電量問題。 本題還有一些細節需要注意。

AC代碼：
[cpp]
#include<iostream> 
#include<algorithm> 
#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
#include<queue> 
#include<math.h> 
#include<climits> 
#define MAXN 105 
#define INF 1000 
using namespace std; 
int map[MAXN][MAXN],w[MAXN],v[MAXN],used[MAXN],dp[505005]; 
int max(int a,int b) {return a>b?a:b;} 
int main() 
{ 
//  freopen("in.txt","r",stdin); 
    int i,j,n,m,t,a,b,c,topv,f=0; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d%d",&n,&m); 
        for(i=0;i<=n;i++) 
        { 
            for(j=0;j<=n;j++)  
                map[i][j]=1000; 
            map[i][i]=0; 
        } 
        for(i=0;i<m;i++) 
        { 
            scanf("%d%d%d",&a,&b,&c); 
            if(c<map[a][b]) map[a][b]=map[b][a]=c;//注意重邊  
        } 
        topv=0; 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&v[i]); 
            topv+=v[i]; 
        } 
        f=topv%2;//注意討論總電量的奇偶問題！  
        topv=(topv+1)/2; 
         
        for(i=0;i<=n;i++) w[i]=map[0][i]; 
        memset(used,0,sizeof(used));    used[0]=1; 
        int sum=0,sumv=0; 
        for(int u=0;u<n;u++) 
        { 
            int mini=1000,k=0; 
            for(i=1;i<=n;i++) if(!used[i] && mini>w[i]) 
            { 
                mini=w[i]; 
                k=i; 
            } 
            if(k==0) break;  //找不到路徑，退出  
            used[k]=1; sum+=w[k]; sumv+=v[k]; 
            for(i=1;i<=n;i++) if(!used[i] && w[i]>w[k]+map[k][i]) 
            { 
                w[i]=w[k]+map[k][i]; 
            } 
        } 
        if(sumv+f<=topv)//全部能到達的點都不夠一半，輸出。  
        { 
            printf("impossible\n"); 
            continue; 
        } 
         
        memset(dp,0,sizeof(dp)); 
        for(i=1;i<=n;i++) 
        { 
            for(j=sum;j>=w[i];j--) 
            { 
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]); 
            } 
        } 
         
        int ans=0; 
        for(i=0;i<=sum;i++) if(dp[i]+f>topv) 
        { 
            ans=i; 
            break; 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 
}