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;
					else
						a[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");
		else
			printf("%d\n", ans);
	}
	return 0;
}

HDU 3339 In Action 价值为最短路的背包,布布扣,bubuko.com

HDU 3339 In Action 价值为最短路的背包

原文：http://blog.csdn.net/u011686226/article/details/23002755