Hdu 3339 In Action[最短路+01背包]

題目連結：點選打開連結

由于最近又學習了一下最短路，開始切了幾道題。

有很多人，估計一開始的都會了解錯題意，這題的題意是，在0點有n多的tank，我們需要摧毀一些電廠，電廠有一定的電力，總體摧毀一半以上才算成功，否則就是失敗。

如果摧毀成功的話，就輸出最小的耗油量。

這道題竟然是最短路+01背包，好給力，唯一的遺憾就是沒有想到，自己一開始也是有那麼一點的一閃而過的念頭，但是就是一閃，沒有深入想。

一開始以為是，在最長路下的最短路。我擦，現在都不知道自己會有這麼一個高端的想法，但是也沒有搞出來。

後來，搜到了别人的想法，果然就是一個最短路+01背包。自己曾經有那麼一閃而過的想法。真會是正确的想法。這個問題很值得深思啊。

哎。不說了，直接代碼吧：

狀态方程為：

dp[i][j]=max(dp[i][j],dp[i-1][j-energy[i])表示的是毀掉前i個電廠，花費j的油，最多可以摧毀的能量。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF=0xffffff;
const int N=105;
bool vis[N];
int map[N][N],dis[N],power[N],energy[N];
int n,m,sum;

void Dijkstra(){
    memset(vis,0,sizeof(vis));
    memset(power,0,sizeof(power));
    for(int i=1;i<=n;i++){
        dis[i]=map[0][i];
    }
    dis[0]=0;vis[0]=true;
    //--------------------------
    for(int i=1;i<=n;i++){
        int Bfind=0,tmp=INF;
        for(int j=0;j<=n;j++){
            if(!vis[j]&&dis[j]<tmp){
                Bfind=j;tmp=dis[j];
            }
        }
        //------------------------
        if(Bfind==0) break;
        vis[Bfind]=true;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]>dis[Bfind]+map[Bfind][j]){
                dis[j]=dis[Bfind]+map[Bfind][j];
            }
        }
        //-------------------------
    }
}

void Init(){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++)
        if(i==j) map[i][j]=0;
        else map[i][j]=INF;
    }
}

void Zreo_OnePack(){
    bool flag[N];
    int sumv=0;
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=n;i++){
        if(dis[i]>=INF){
            continue;
        }
        sumv+=dis[i];flag[i]=true;
    }
    int dp[N*N+5];//到底應該開多大的空間？
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        if(flag[i])
        for(int v=sumv;v>=dis[i];v--)
        dp[v]=max(dp[v],dp[v-dis[i]]+energy[i]);
    }
    int ans=-1;
    for(int i=1;i<=sumv;i++){
        if(dp[i]>sum/2) {
            ans=i;
            break;
        }
    }
    if(ans==-1) printf("impossible\n");
    else printf("%d\n",ans);
}
int main(){
//    freopen("1.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        Init();
        for(int i=1;i<=m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(map[a][b]>c){//重邊.
                map[a][b]=c;map[b][a]=c;
            }
        }
        sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&energy[i]);
            sum+=energy[i];
        }
        energy[0]=0;
        Dijkstra();
        Zreo_OnePack();
    }
    return 0;
}
           

今天晚上有學長講查分限制，正好和這段的學習有關。恩，先看看吧。。