首页 > 代码库 > hdu--4856--状压dp
hdu--4856--状压dp
我都不想将bfs这3个字写在标题里...bfs没那么简单
就是求出任意两个管子之间的最短距离 但这边不能直接用spfa dij啊什么的 但感觉现在的bfs就有点相当于退化版的最短路。。
这题的重点还是在完成上面的Precompute后 接下去的求tsp操作
这边应该是最简单的 没有多余的难度增加的求tsp
我这提供了2种 我分别加上注释
tot 就是总的状态
1 for( int i = 2 ; i<=tot ; i++ )//枚举状态 2 { 3 for( int j = 1 ; j<=m ; j++ )//枚举管子 4 { 5 if( i&(1<<j) ) //在该状态下已经走过 6 continue; 7 for( int k = 1 ; k<=m ; k++ ) 8 { 9 if( i&(1<<k) ) //在该状态下已经走过 去 未达到的管子10 dp[ i|(1<<j) ][j] = min( dp[ i|(1<<j) ][j] , dp[i][k]+dist[k][j] );11 } 12 }13 }
1 for( int i = 2 ; i<=tot ; i++ )//枚举状态 2 { 3 for( int j = 1 ; j<=m ; j++ )//枚举管子 4 { 5 if( i&(1<<j) )//从该状态下已经到达的管子出发 6 { 7 for( int k = 1 ; k<=m ; k++ ) 8 { 9 if( !( i&(1<<k) ) )//从该状态下已经到达的管子出发 去 还没有到达的管子10 dp[ i|(1<<k) ][k] = min( dp[ i|(1<<k) ][k] , dp[i][j] + dist[j][k] );11 }12 }13 }14 }
其实2者没什么差 就是写法上有点区别 我觉得第二种写法更好.
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 7 int n , m , tot; 8 const int size = 20; 9 const int inf = 0x3f3f3f3f; 10 int dir[4][2] = {1,0,-1,0,0,1,0,-1}; 11 int dp[1<<16][size]; 12 bool vis[size][size]; 13 int dist[size][size]; 14 char mp[size][size]; 15 16 struct data 17 { 18 int sx , sy , endx , endy; 19 int step; 20 data(){}; 21 data( int u , int v , int w ):endx(u),endy(v),step(w){}; 22 }pipe[size]; 23 24 void init( ) 25 { 26 memset( dp , inf , sizeof(dp) ); 27 for( int i = 1 ; i<=m ; i++ ) 28 dp[1<<i][i] = 0; 29 } 30 31 int bfs( int from , int to ) 32 { 33 queue<data> q; 34 data now; 35 now.endx = pipe[from].sx; 36 now.endy = pipe[from].sy; 37 now.step = 0; 38 q.push( now ); 39 memset( vis , false , sizeof(vis) ); 40 vis[ now.endx ][ now.endy ] = true; 41 while( !q.empty( ) ) 42 { 43 now = q.front(); 44 q.pop(); 45 if( now.endx == pipe[to].endx && now.endy == pipe[to].endy ) 46 { 47 return now.step; 48 } 49 for( int i = 0 ; i<4 ; i++ ) 50 { 51 int xx = now.endx + dir[i][0]; 52 int yy = now.endy + dir[i][1]; 53 if( xx >=1 && xx<=n && yy>=1 && yy<=n && mp[xx][yy]!=‘#‘ && !vis[xx][yy] ) 54 { 55 vis[xx][yy] = true; 56 q.push( data(xx,yy,now.step+1) ); 57 } 58 } 59 } 60 return inf; 61 } 62 63 void solve( ) 64 { 65 for( int i = 1 ; i<=m ; i++ ) 66 { 67 for( int j = 1 ; j<=m ; j++ ) 68 { 69 if( i==j ) 70 dist[i][j] = 0; 71 else 72 dist[i][j] = bfs( i , j ); 73 } 74 } 75 for( int i = 2 ; i<=tot ; i++ ) 76 { 77 for( int j = 1 ; j<=m ; j++ ) 78 { 79 if( i&(1<<j) ) 80 continue; 81 for( int k = 1 ; k<=m ; k++ ) 82 { 83 if( i&(1<<k) ) 84 dp[ i|(1<<j) ][j] = min( dp[ i|(1<<j) ][j] , dp[i][k]+dist[k][j] ); 85 } 86 } 87 } 88 } 89 90 int main() 91 { 92 cin.sync_with_stdio(false); 93 int ans; 94 while( cin >> n >> m ) 95 { 96 init( ); 97 for( int i = 1 ; i<=n ; i++ ) 98 { 99 for( int j = 1 ; j<=n ; j++ )100 {101 cin >> mp[i][j];102 }103 }104 for( int i = 1 ; i<=m ; i++ )105 {106 cin >> pipe[i].sx >> pipe[i].sy >> pipe[i].endx >> pipe[i].endy; 107 }108 tot = ( 1<<(m+1) ) - 2;109 init( );110 solve( );111 ans = inf;112 for( int i = 1 ; i<=m ; i++ )113 {114 ans = min( ans , dp[ tot ][i] );115 }116 if( ans==inf )117 cout << -1 << endl;118 else119 cout << ans << endl;120 }121 return 0;122 }
today:
first love
hdu--4856--状压dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。