首页 > 代码库 > HDU 5067 (状态压缩DP+TSP)
HDU 5067 (状态压缩DP+TSP)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5067
题目大意:蓝翔挖掘机挖石子。把地图上所有石子都运回起点,问最少耗时。
解题思路:
首先得YY出来。
最少耗时肯定是从起点出发,把所有石子点走一遍且只走一遍,把石子装在车上,然后最后回到起点。
由于石子堆最多也就10个。不难看出这就是个裸的TSP。
首先BFS计算出每个石子间的最短路。
然后进行TSP就行了。
起点的石子无所谓。所以TSP的起点就是(1,1)。
#include "cstdio"#include "iostream"#include "cstring"#include "vector"#include "queue"using namespace std;#define inf 0x3f3f3f3fint area[55][55],dp[1<<15][15],vis[55][55],dis[55][55],dir[4][2]={-1,0,1,0,0,-1,0,1},n,m,g;struct status{ int x,y,dep; status(int x,int y,int dep):x(x),y(y),dep(dep) {}};int bfs(status s,status e){ memset(vis,0,sizeof(vis)); vis[s.x][s.y]=true; queue<status> Q; Q.push(status(s.x,s.y,0)); while(!Q.empty()) { status t=Q.front();Q.pop(); for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1]; if(X<1||X>n||Y<1||Y>m||vis[X][Y]) continue; vis[X][Y]=true; if(X==e.x&&Y==e.y) return t.dep+1; Q.push(status(X,Y,t.dep+1)); } }}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { vector<status> stone; stone.push_back(status(1,1,0)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&g); if(i==1&&j==1) continue; if(g) stone.push_back(status(i,j,0)); } for(int i=0;i<stone.size();i++) { for(int j=0;j<stone.size();j++) { if(i==j) dis[i][j]=0; else {if(!dis[i][j]) dis[i][j]=dis[j][i]=bfs(stone[i],stone[j]);} } } int s=stone.size(); int cnt=1<<s; for(int i=0;i<cnt;i++) { for(int j=0;j<s;j++) { if(!i&(1<<j)) continue; if(i==(1<<j)) dp[i][j]=dis[0][j]; else { dp[i][j]=inf; for(int k=0;k<s;k++) if(i&(1<<k)&&k!=j) dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+dis[k][j]); } } } int ans=inf; for(int i=0;i<s;i++) ans=min(ans,dp[cnt-1][i]+dis[i][0]); printf("%d\n",ans); memset(dp,0,sizeof(dp)); memset(dis,0,sizeof(dis)); }}
11906643 | 2014-10-18 22:12:42 | Accepted | 5067 | 31MS | 2200K | 2159 B | C++ | Physcal |
HDU 5067 (状态压缩DP+TSP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。