HDU3339 Floyd+01背包

题意：给定一张图，每个点都有一个power值，到每个点都要一定的距离 消耗一定的油量，求从0出发到某些点 使得 油量消耗最少且power值达到一半。

可以floyd或者spfa求出0到各点的距离 dis[ maxm ]。

然后就可以转化为：从dis[]中挑出某些点，使得距离和最小且power值达到某个值。

从01背包中可以发现：从给定的一些物品中挑出一些放入一个背包中，使得不超过背包体积。

这是我们可以把dis当做每个物品的体积，power当做价值。

然后从dp中搜到一个power值满足条件的最小的 i 即可

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 105;
const int maxm = 1000005;
const int inf = 99999999;
int mat[ maxn ][ maxn ],power[ maxn ],dis[ maxn ];
int dp[ maxm ];
int sum,aim;
//power 相当于价值，dis 相当于体积
void init( int n ){
    for( int i=0;i<=n;i++ )
        for( int j=0;j<=n;j++ )
            mat[ i ][ j ]=inf;
}
void floyd( int n ){
    for( int k=0;k<=n;k++ ){
        for( int i=0;i<=n;i++ ){
            for( int j=0;j<=n;j++ ){
                if( mat[i][k]!=inf&&mat[k][j]!=inf&&mat[i][j]>mat[i][k]+mat[k][j] ){
                    mat[i][j]=mat[i][k]+mat[k][j];
                }
            }
        }
    }
    for( int i=1;i<=n;i++ ){
        dis[i]=mat[0][i];
        if( dis[i]!=inf )
            sum+=dis[i];
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while( T-- ){
        int n,m;
        scanf("%d%d",&n,&m);
        init( n );
        int a,b,c;
        while( m-- ){
            scanf("%d%d%d",&a,&b,&c);
            mat[ a ][ b ]=mat[ b ][ a ]=min(mat[a][b],c);
        }
        sum=aim=0;
        for( int i=1;i<=n;i++ ){
            scanf("%d",&power[ i ]);
            aim+=power[ i ];
        }
        floyd( n );
        //dp
        //sum/=2;
        memset( dp,0,sizeof( dp ));
        for( int i=1;i<=n;i++ ){
            for( int j=sum;j>=dis[i];j-- ){
                dp[ j ]= max( dp[ j ],dp[ j-dis[i] ]+power[ i ] );
            }
        }
        int ans=inf;
        for( int i=0;i<=sum;i++ )
            if( dp[i]>=(aim/2+1)&&dp[i]<ans ){
                ans=i;
                break;
            }
        if( ans==inf )
            printf("impossible\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}