http://poj.org/problem?id=2288

題意：

有n個島嶼，每個島嶼有一個權(quán)值V，一條哈密頓路徑C1，C2，...Cn的值為3部分之和：

第1部分，將路徑中每個島嶼的權(quán)值累加起來；第2部分，對路徑中的每條邊（Ci，Ci+1），將成績Vi×Vi+1累加起來；第3部分，當(dāng)路徑中連續(xù)的3個島嶼Ci、Ci+1和Ci+2形成一個三角形，即在島嶼Ci和Ci+2之間有一座橋，則把乘積Vi×Vi+1×Vi+2累加起來。

尋找權(quán)值最大的哈密頓路徑和其路徑數(shù)。

?

思路：

用d【status】【i】【j】表示當(dāng)前狀態(tài)為status，并且最后兩個頂點分別為 i 和 j 時的最大權(quán)值，同理，ways【status】【i】【j】表示此時對應(yīng)的路徑的數(shù)量。

1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 1000 + 5; 17 18 int n, m; 19 20 int val[13]; 21 int g[13][13]; 22 ll d[1<<13][13][13]; 23 ll ways[1<<13][13][13]; 24 25 int main() 26 { 27 //freopen("in.txt","r",stdin); 28 int T; 29 scanf("%d",&T); 30 while(T--) 31 { 32 memset(g,0,sizeof(g)); 33 memset(d,-1,sizeof(d)); 34 memset(ways,0,sizeof(ways)); 35 36 scanf("%d%d",&n,&m); 37 for(int i=0;i<n;i++) scanf("%d",&val[i]); 38 for(int i=0;i<m;i++) 39 { 40 int u, v; 41 scanf("%d%d",&u, &v); 42 u--; v--; 43 g[u][v]=g[v][u]=1; 44 //初始化 45 d[(1<<u)|(1<<v)][u][v]=d[(1<<u)|(1<<v)][v][u]=val[u]+val[v]+val[u]*val[v]; 46 ways[(1<<u)|(1<<v)][u][v]=ways[(1<<u)|(1<<v)][v][u]=1; 47 } 48 49 ll maxvalue=-1; 50 ll maxways=0; 51 52 if(n==1) {maxvalue=val[0];maxways=1;} //如果只有一個頂點，則特判 53 54 if(n!=1) 55 for(int s=0;s<(1<<n);s++) 56 { 57 for(int i=0;i<n;i++) 58 { 59 if(s&(1<<i)) 60 for(int j=0;j<n;j++) 61 { 62 if((i!=j) && (s&(1<<j)) &&d[s][i][j]>-1) 63 { 64 for(int k=0;k<n;k++) //枚舉新加入的頂點 65 { 66 if(!(s&(1<<k)) && g[j][k]) 67 { 68 int nextstatus=s|(1<<k); 69 ll tmp = d[s][i][j]+val[k]+val[j]*val[k]; 70 if(g[i][k]) //如果Ci和Ci+2之間存在橋 71 tmp+=val[i]*val[j]*val[k]; 72 73 if(d[nextstatus][j][k]==tmp) 74 { 75 ways[nextstatus][j][k]+=ways[s][i][j]; 76 } 77 else if(d[nextstatus][j][k]<tmp) 78 { 79 d[nextstatus][j][k]=tmp; 80 ways[nextstatus][j][k]=ways[s][i][j]; 81 } 82 } 83 } 84 } 85 } 86 } 87 } 88 89 int s=(1<<n)-1; 90 if(n!=1) 91 for(int i=0;i<n;i++) 92 { 93 for(int j=0;j<n;j++) 94 { 95 if(g[i][j]==0) continue; 96 if(d[s][i][j]>maxvalue) 97 { 98 maxvalue=d[s][i][j]; 99 maxways=ways[s][i][j]; 100 } 101 else if(d[s][i][j]==maxvalue) 102 maxways+=ways[s][i][j]; 103 } 104 } 105 if(n!=1) maxways/=2; //因為正向和逆向是一樣的，所以這里除2 106 if(maxvalue==-1) puts("0 0"); 107 else printf("%lld %lld\n",maxvalue,maxways); 108 } 109 return 0; 110 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zyb993963526/p/7198529.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2288 Islands and Bridges（状压dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。