首页 > 代码库 > HDU 4856 (状态压缩DP+TSP)
HDU 4856 (状态压缩DP+TSP)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4856
题目大意：有一个迷宫。迷宫里有些隧道，每个隧道有起点和终点，在隧道里不耗时。出隧道就耗时，你的任务是访问完所有隧道且仅一次，求最短耗时。
解题思路：
暑假练习的时候。把英文读了N遍也没理解题意。
其实就是个最后不回到开头的TSP。
首先求BFS求两两隧道之间的最短路，注意BFS的起点是隧道i的终点，BFS的终点是隧道j的起点。
一定要特判一下两个隧道终点和起点是否一样，如果一样话dis=0, 我因为BFS没注意这个WA了10几次。
PS. 根据esxgx大神的说法，所有最短路算法(Dijkstra or Bellman-Ford)在每两个点距离为1的时候都会退化成普通的BFS，于是你在这里相当于手艹了个最短路。
然后就是对所有隧道进行TSP。
dp[i][j]表示状态i时，在j点的最少耗时，然后就是赤裸裸的TSP了。TSP的写法不唯一，我从别人那扒的这种TSP稍微快点。
#include "cstdio"#include "string"#include "iostream"#include "cstring"#include "queue"#include "vector"using namespace std;int n,m,vis[20][20],dis[20][20],dir[4][2]={-1,0,1,0,0,-1,0,1},ans,dp[1<<15][20];char map[20][20];const int inf=0x3f3f3f3f;struct status{ int x,y,dep; status(int x,int y,int dep):x(x),y(y),dep(dep) {}};struct tunnel{ int sx,sy,ex,ey;}T[25];int bfs(status a,status b){ if(a.x==b.x&&a.y==b.y) return 0; //关键一步,如果两个隧道恰好拼在一起，则dis=0 memset(vis,0,sizeof(vis)); int ans=inf; queue<status> Q; Q.push(a); vis[a.x][a.y]=true; 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>n||vis[X][Y]||map[X][Y]!=‘.‘) continue; vis[X][Y]=true; if(X==b.x&&Y==b.y) {ans=min(ans,t.dep+1);return ans;} Q.push(status(X,Y,t.dep+1)); } } return ans;}int main(){ ios::sync_with_stdio(false); string tt; while(cin>>n>>m) { memset(dis,0,sizeof(dis)); for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) map[i][j+1]=tt[j]; } for(int i=1;i<=m;i++) cin>>T[i].sx>>T[i].sy>>T[i].ex>>T[i].ey; for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) { if(i==j) {dis[i][j]=0;} else dis[i][j]=bfs(status(T[i].ex,T[i].ey,0),status(T[j].sx,T[j].sy,0)); } int cnt=1<<m,res=inf; for(int i=0;i<cnt;i++) { for(int j=1;j<=m;j++) { int s=(1<<(j-1)); if((i&s)==0) continue; if(i==s) dp[i][j]=0; else dp[i][j]=inf; for(int k=1;k<=m;k++) { int t=(1<<(k-1)); if((i&t)==0||k==j||dis[k][j]==inf) continue; dp[i][j]=min(dp[i][j],dp[i^s][k]+dis[k][j]); } if(i==cnt-1) res=min(res,dp[i][j]); } } if(res==inf) printf("-1\n"); else printf("%d\n",res); }}
| 11887989 | 2014-10-16 20:17:15 | Accepted | 4856 | 171MS | 2852K | 2290 B | C++ | Physcal |
HDU 4856 (状态压缩DP+TSP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。