首页 > 代码库 > hdu--3001--类似旅行商<tsp>
hdu--3001--类似旅行商<tsp>
里面包含了很多内容的一道题 可以学到很多
题意 很简单 就是一个人 要绕城市一圈 不必回到起点 但是每个城市都要经过 并且最多每个重复走2次
注意 城市数量是 <=10的 如果 你以前就遇到过 类似的题 肯定能很快反应过来 状压dp 在某一维开个3维数组 0 1 2分别城市在该状态下经过某城市的次数为多少
所以 就是个 三进制的压缩 蛮好的 以前只听过二进制 我孤陋寡闻了 =_=
dp转移方程很简单 主要是 枚举状态的时候 各种细节要注意
dp[ state+three[j] ][j] = min( dp[ state+three[j] ][j] , dp[ state ][i] + mp[i][j] );
因为 城市个数实在是太水了 就用最简单的 二维矩阵存储吧 但会有重边 需要更新取最小值
for( int i = 0 ; i<n ; i++ ){ dp[ three[i] ][i] = 0;}
这是个很重要的初始化 因为 我们没有固定从哪个点出发 那就表示 任意一点都可以当做起点
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int n; 7 const int inf = 0X3f3f3f; 8 const int v = 60000; 9 const int size = 11;10 int dp[v][size] , vis[v][size];11 int mp[size][size];12 int three[size];13 14 void init( )15 {16 int num;17 three[0] = 1;18 for( int i = 1 ; i<size ; i++ )19 {20 three[i] = three[i-1] * 3;21 }22 for( int i = 1 ; i<three[size-1] ; i++ )23 {24 num = i;25 for( int j = 0 ; j<size-1 ; j++ )26 {27 vis[i][j] = num % 3;28 num /= 3;29 }30 }31 }32 33 int solve( )34 {35 bool flag;36 int ans = inf;37 for( int state = 1 ; state<three[n] ; state++ )38 {39 flag = true;40 for( int i = 0 ; i<=n-1 ; i++ )41 {42 if( !vis[state][i] )43 flag = false;44 if( dp[state][i] == inf )45 continue;46 for( int j = 0 ; j<=n-1 ; j++ )47 {48 if( i==j || mp[i][j] == inf || vis[state][j]>=2 )49 continue;50 dp[ state+three[j] ][j] = min( dp[ state+three[j] ][j] , dp[ state ][i] + mp[i][j] );51 }52 }53 if( flag )54 {55 for( int i = 0 ; i<=n-1 ; i++ )56 {57 ans = min( ans , dp[state][i] );58 }59 }60 }61 return ans;62 }63 64 int main()65 {66 cin.sync_with_stdio(false);67 int m , a , b , c;68 int ans;69 init( );70 while( cin >> n >> m )71 {72 memset( dp , inf , sizeof(dp) );73 memset( mp , inf , sizeof(mp) );74 for( int i = 0 ; i<n ; i++ )75 {76 dp[ three[i] ][i] = 0;77 }78 while( m-- )79 {80 cin >> a >> b >> c;81 -- a;82 -- b;83 mp[a][b] = mp[b][a] = min( mp[a][b] , c );84 }85 ans = solve( );86 if( ans == inf )87 cout << -1 << endl;88 else89 cout << ans << endl;90 }91 return 0;92 }
today:
忍受某段时光
然后会被自己感动
hdu--3001--类似旅行商<tsp>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。