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         else
119             cout << ans << endl;
120     }
121     return 0;
122 }

View Code

today:

　　first love