首页 > 代码库 > POJ 2288 Islands and Bridges（状压dp）
POJ 2288 Islands and Bridges（状压dp）
http://poj.org/problem?id=2288
题意：
有n个岛屿，每个岛屿有一个权值V，一条哈密顿路径C1，C2，...Cn的值为3部分之和：
第1部分，将路径中每个岛屿的权值累加起来；第2部分，对路径中的每条边（Ci，Ci+1），将成绩Vi×Vi+1累加起来；第3部分，当路径中连续的3个岛屿Ci、Ci+1和Ci+2形成一个三角形，即在岛屿Ci和Ci+2之间有一座桥，则把乘积Vi×Vi+1×Vi+2累加起来。
寻找权值最大的哈密顿路径和其路径数。
思路：
用d【status】【i】【j】表示当前状态为status，并且最后两个顶点分别为 i 和 j 时的最大权值，同理，ways【status】【i】【j】表示此时对应的路径的数量。
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=http://www.mamicode.com/-1; 50 ll maxways=0; 51 52 if(n==1) {maxvalue=http://www.mamicode.com/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=http://www.mamicode.com/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; //因为正向和逆向是一样的，所以这里除2106 if(maxvalue=http://www.mamicode.com/=-1) puts("0 0");107 else printf("%lld %lld\n",maxvalue,maxways);108 }109 return 0;110 }
POJ 2288 Islands and Bridges（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。