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;
}
           

今天晚上有学长讲查分约束，正好和这段的学习有关。恩，先看看吧。。