首页 > 代码库 > HDU 4568 Hunter 最短路+状压DP
HDU 4568 Hunter 最短路+状压DP
题意：给一个n*m的格子，格子中有一些数，如果是正整数则为到此格子的花费，如果为-1表示此格子不可到，现在给k个宝藏的地点(k<=13),求一个人从边界外一点进入整个棋盘，然后拿走所有能拿走的宝藏的最小花费，如果一次不能拿走所有能拿到的或者根本拿不到任何宝藏，输出0.
解法：看到k的范围应该想到状态压缩，将每个格子都看成一个点，再新建两个点，一个表示边界外的起点，用0表示，一个表示边界外的终点，用n*m+1表示，然后相互建边，建有向边，边权为终点格子的花费值，（其实都不用建边，直接跑最短路也行）然后求这k+2个点两两之间的最短距离，然后就化成TSP问题了，用状压DP可以解决。
求k+2个点两两之间的最短距离可以跑k+2次SPFA求出，复杂度不高。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007using namespace std;#define N 10007int mp[304][304];int C[304][304];int dis[20][20];int n,m,k;int d[50005];struct node{ int v,w,next;}G[4*50005];int head[4*50005],tot;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int vis[50006];struct Point{ int x,y;}P[15];int OK(int nx,int ny){ if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) return 1; return 0;}void addedge(int u,int v,int w){ G[tot].v = v; G[tot].w = w; G[tot].next = head[u]; head[u] = tot++;}void SPFA(int s){ queue<int> que; while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); vis[s] = 1; que.push(s); for(int i=0;i<=n*m+1;i++) d[i] = Mod; d[s] = 0; while(!que.empty()) { int u = que.front(); que.pop(); vis[u] = 0; for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; int w = G[i].w; if(d[v] > d[u] + w) { d[v] = d[u] + w; if(!vis[v]) { vis[v] = 1; que.push(v); } } } }}int dp[1<<17][20];int main(){ int i,j; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&C[i][j]); if(C[i][j] == -1) C[i][j] = Mod; } memset(head,-1,sizeof(head)); tot = 0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { int now = (i-1)*m + j; for(int h=0;h<4;h++) { int kx = i + dx[h]; int ky = j + dy[h]; if(!OK(kx,ky)) continue; int tmp = (kx-1)*m + ky; addedge(now,tmp,C[kx][ky]); } if(i == 1 || i == n || j == 1 || j == m) { addedge(0,now,C[i][j]); addedge(now,n*m+1,0); } } } scanf("%d",&k); P[0].x = 1, P[0].y = 0; P[k+1].x = n,P[k+1].y = m+1; for(i=1;i<=k;i++) scanf("%d%d",&P[i].x,&P[i].y),P[i].x++,P[i].y++; for(i=0;i<=k+1;i++) { int s = (P[i].x-1)*m + P[i].y; SPFA(s); for(j=0;j<=k+1;j++) { if(i == j) continue; int v = (P[j].x-1)*m + P[j].y; dis[i][j] = d[v]; } } for(i=0;i<(1<<16);i++) { for(j=0;j<16;j++) dp[i][j]=Mod; } for(i=0;i<k;i++) { dp[1<<i][i+1]=dis[0][i+1]; } for(i=0;i<(1<<k);i++) { for(int kk=0;kk<k;kk++) { if(!(i&(1<<kk)))continue; for(int j=0;j<k;j++) { if(i&(1<<j)) continue; dp[i+(1<<j)][j+1]=min(dp[i+(1<<j)][j+1],dp[i][kk+1]+dis[kk+1][j+1]); } } } int minn=Mod; for(i=1;i<=k;i++) minn=min(dp[(1<<k)-1][i]+dis[i][k+1],minn); if(minn == Mod) cout<<0<<endl; else cout<<minn<<endl; } return 0;}
HDU 4568 Hunter 最短路+状压DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。