首页 > ACM题库 > HDU-杭电 > HDU 4284-Travel-动态规划-[解题报告]HOJ
2015
05-23

HDU 4284-Travel-动态规划-[解题报告]HOJ

Travel

问题描述 :

  PP loves travel. Her dream is to travel around country A which consists of N cities and M roads connecting them. PP has measured the money each road costs. But she still has one more problem: she doesn’t have enough money. So she must work during her travel. She has chosen some cities that she must visit and stay to work. In City_i she can do some work to earn Ci money, but before that she has to pay Di money to get the work license. She can’t work in that city if she doesn’t get the license but she can go through the city without license. In each chosen city, PP can only earn money and get license once. In other cities, she will not earn or pay money so that you can consider Ci=Di=0. Please help her make a plan to visit all chosen cities and get license in all of them under all rules above.
  PP lives in city 1, and she will start her journey from city 1. and end her journey at city 1 too.

输入:

  The first line of input consists of one integer T which means T cases will follow.
  Then follows T cases, each of which begins with three integers: the number of cities N (N <= 100) , number of roads M (M <= 5000) and her initiative money Money (Money <= 10^5) .
  Then follows M lines. Each contains three integers u, v, w, which means there is a road between city u and city v and the cost is w. u and v are between 1 and N (inclusive), w <= 10^5.
  Then follows a integer H (H <= 15) , which is the number of chosen cities.
  Then follows H lines. Each contains three integers Num, Ci, Di, which means the i_th chosen city number and Ci, Di described above.(Ci, Di <= 10^5)

输出:

  The first line of input consists of one integer T which means T cases will follow.
  Then follows T cases, each of which begins with three integers: the number of cities N (N <= 100) , number of roads M (M <= 5000) and her initiative money Money (Money <= 10^5) .
  Then follows M lines. Each contains three integers u, v, w, which means there is a road between city u and city v and the cost is w. u and v are between 1 and N (inclusive), w <= 10^5.
  Then follows a integer H (H <= 15) , which is the number of chosen cities.
  Then follows H lines. Each contains three integers Num, Ci, Di, which means the i_th chosen city number and Ci, Di described above.(Ci, Di <= 10^5)

样例输入:

2
4 5 10
1 2 1
2 3 2
1 3 2
1 4 1
3 4 2
3
1 8 5
2 5 2
3 10 1
2 1 100
1 2 10000
1
2 100000 1

样例输出:

YES
NO

转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by—cxlove 

题目:给出一些城市,从1出发,旅游一圈回到1,由于花费可能不够,所以选择一些城市打工,打工之前需要花费d买一个证,工资为c。选中的城市必须去工作一次,而且只能工作一次,问能不能完成旅行

http://acm.hdu.edu.cn/showproblem.php?pid=4284 

比赛的时候,卡了很久,当时队友用SPFA+状态DP+堆栈写的,主要是把一点考虑错了

当时把C和D合并了,其实是不对的,因为首先是要购买证,然后才能工作,否则拿不到工资。

也就是先要判断够不够买证的钱D,然后才能拿到工资。

跪舔,先用Floyd预处理最短路n^3,然后状态DP,h*h*2^h,4S+,效率很低的做法

可以用队列,堆栈加速

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#define inf 1<<28
#define N 105
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int n,m,money,h;
int path[N][N];
int dp[20][1<<16];
int work[20],c[20],d[20];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&money);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)
				path[i][j]=inf;
			path[i][i]=0;
		}
		for(int i=0;i<m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			u--;v--;
			path[u][v]=Min(path[u][v],w);
			path[v][u]=path[u][v];
		}
		//Floyd预处理
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
					if(i!=k&&i!=j&&j!=k)
						path[i][j]=Min(path[i][k]+path[k][j],path[i][j]);
		scanf("%d",&h);
		int pos=-1;
		for(int i=0;i<h;i++){
			scanf("%d%d%d",&work[i],&c[i],&d[i]);
			work[i]--;
			if(work[i]==0) pos=i;   //说明必需点中包含了起点1
		}
		//如果不包含,我们加入冗余点,便于后面处理,c和d都为0
		if(pos==-1){
			work[h]=0;c[h]=0;d[h]=0;
			pos=h++;
		}
		memset(dp,-1,sizeof(dp));
		if(money-d[pos]>=0) dp[pos][1<<pos]=money-d[pos]+c[pos];dp[pos][0]=money;
		for(int i=0;i<(1<<h);i++){
			for(int j=0;j<h;j++){
				if(dp[j][i]==-1) continue;
				for(int k=0;k<h;k++){
					if(k==j||((1<<k)&i)) continue;
					//钱够在两个城市之间移动,而且够买证
					if(dp[j][i]>=path[work[j]][work[k]]+d[k])
						dp[k][i|(1<<k)]=Max(dp[k][i|(1<<k)],dp[j][i]-path[work[j]][work[k]]-d[k]+c[k]);
				}
			}
		}
		bool ans=false;
		for(int i=0;i<h;i++)
			//最后判断能不能返回起点
			if(dp[i][(1<<h)-1]>=path[work[i]][0]){
				ans=true;
				break;
			}
		puts(ans?"YES":"NO");
	}
	return 0;
}
			

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7963286