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

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