HDU 4284 Travel(12年天津 状态DP)
转载请注明出处，谢谢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都为0if(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;}