HDU 3339 In Action 答题报告（最短路+背包）

HDU 3339 In Action 解题报告（最短路+背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3339

晚上看图论500的时候看到一个最短路+背包的题，有点感兴趣，于是花了一个多小时A了这题。

题目大意：*欲炸地球，引爆核弹需要用一半的电。而电分布在不同的电站。每个电站都存有不同的电。目的是派出坦克，毁坏电站，使其无法引爆。

给出无向图，要求以最小总距离，毁坏一半以上的电。 注意每个电站都需要一个坦克。

每个电站都有自己的花费（0到它的最短路），以及价值（电量）。于是转化为最少的花费去点一半以上电量问题。 本题还有一些细节需要注意。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<math.h>
#include<climits>
#define MAXN 105
#define INF 1000
using namespace std;
int map[MAXN][MAXN],w[MAXN],v[MAXN],used[MAXN],dp[505005];
int max(int a,int b) {return a>b?a:b;}
int main()
{
//	freopen("in.txt","r",stdin);
	int i,j,n,m,t,a,b,c,topv,f=0;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++) 
				map[i][j]=1000;
			map[i][i]=0;
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			if(c<map[a][b]) map[a][b]=map[b][a]=c;//注意重边 
		}
		topv=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&v[i]);
			topv+=v[i];
		}
		f=topv%2;//注意讨论总电量的奇偶问题！ 
		topv=(topv+1)/2;
		
		for(i=0;i<=n;i++) w[i]=map[0][i];
  		memset(used,0,sizeof(used));	used[0]=1;
  		int sum=0,sumv=0;
		for(int u=0;u<n;u++)
		{
			int mini=1000,k=0;
			for(i=1;i<=n;i++) if(!used[i] && mini>w[i])
			{
				mini=w[i];
				k=i;
			}
			if(k==0) break;  //找不到路径，退出 
			used[k]=1; sum+=w[k]; sumv+=v[k];
			for(i=1;i<=n;i++) if(!used[i] && w[i]>w[k]+map[k][i])
			{
				w[i]=w[k]+map[k][i];
			}
		}
		if(sumv+f<=topv)//全部能到达的点都不够一半，输出。 
		{
			printf("impossible\n");
			continue;
		}
		
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
		{
			for(j=sum;j>=w[i];j--)
			{
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		
		int ans=0;
		for(i=0;i<=sum;i++) if(dp[i]+f>topv)
		{
			ans=i;
			break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

1楼wangqiuyun昨天 21:49

顶起