简单的状压$dp$,
和P1171 售货员的难题简直一模一样(但也正因为此把我坑了)
令$f[i][j]$表示状态$i$,最后在$j$的最短路最长路(又坑了我)
有$$f[i][j] = maxleft{f[i-left { j ight }][k]+dis[k][j];;|;;kin (i-left { j ight }) ight}$$
!!要初始化为极小值!!(不初始化只有$46pts$)
!!边界!!$$f[i][0] = 0$$
枚举时可以只枚举奇数的状态(因为$0$号点必选)
上代码
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #define ll long long 6 using namespace std; 7 8 template <typename T> void in(T &x) { 9 x = 0; T f = 1; char ch = getchar(); 10 while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} 11 while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();} 12 x *= f; 13 } 14 15 template <typename T> void out(T x) { 16 if(x < 0) x = -x , putchar('-'); 17 if(x > 9) out(x/10); 18 putchar(x%10 + 48); 19 } 20 //------------------------------------------------------- 21 22 const int N = 20; 23 24 int n,m; 25 int a[N][N]; 26 int f[1<<N][N]; 27 28 int main() { 29 int i,j,k,u,v; 30 in(n); in(m); 31 for(i = 0;i < m; ++i) { 32 in(u); in(v); in(a[u][v]); 33 } 34 memset(f,~0x3f,sizeof(f));//debug 要赋极小值 35 f[1][0] = 0;//!边界! 36 for(i = 3;i < (1<<n); i += 2) { 37 f[i][0] = 0;//!边界! 38 for(j = 0;j < n; ++j) { 39 if(!(i&(1<<j))) continue; 40 for(k = 0;k < n; ++k) { 41 if(!a[k][j] || !(i&(1<<k))) continue; 42 f[i][j] = max(f[i][j],f[i^(1<<j)][k]+a[k][j]); 43 } 44 } 45 } 46 //out(f[(1<<n)-1][n-1]);//debug 47 int ans = 0; 48 for(i = 1|(1<<n-1);i < (1<<n); i += 2) ans = max(ans,f[i][n-1]); 49 out(ans); 50 return 0; 51 }