本文主要是介绍HDU 3339 In Action 价值为最短路的背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：HDU 3339 In Action
题意：有一个系统要去破坏 该系统是有n个点组成的图 每个点有一个权值
可以从0排除任意个机器人 去占领一个点 每个机器只能占领一个地方 所有机器人占领点的权值之和大于所有点权值之和的一半(不能等于) 就算破环成功
求在破坏的情况下所有机器人走过的路径之和最小
思路：简而言之 就是选出若干个点 他们的和大于总数的一半 并且走的路最短
转化成背包问题 总体积为所有点权值的和 每个物品的体积是该个点的权值 价值是0到个点的距离 0到各个点的距离可以用floyd求出 最后01背包求最小值就可以了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
const int maxm = 10010;
int a[maxn][maxn];
int b[maxn];
int dp[maxm];
int n, m;
void floyd()
{for(int k = 0; k <= n; k++)for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)if(a[i][j] > a[i][k] + a[k][j])a[i][j] = a[i][k] + a[k][j];}int main()
{int T;scanf("%d", &T);while(T--){scanf("%d %d", &n, &m);for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++){if(i == j)a[i][j] = 0;elsea[i][j] = 99999999;}for(int i = 1; i <= m; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);if(a[u][v] > w)a[u][v] = a[v][u] = w;}floyd();int sum = 0;for(int i = 1; i <= n; i++){scanf("%d", &b[i]);sum += b[i];}//printf("%d\n", sum);for(int i = 1; i <= sum; i++)dp[i] = 99999999;dp[0] = 0;for(int i = 1; i <= n; i++){for(int j = sum; j >= b[i]; j--){dp[j] = min(dp[j], dp[j-b[i]]+a[0][i]);}}int ans = 99999999;for(int i = sum/2+1; i <= sum; i++){ans = min(ans, dp[i]);}if(ans == 99999999)puts("impossible");elseprintf("%d\n", ans);}return 0;
}
这篇关于HDU 3339 In Action 价值为最短路的背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
