乐清网站定制公司,网易网站开发,海外服务器ip免费,百度世界排名http://poj.org/problem?id2288 题意#xff1a; 有n个岛屿#xff0c;每个岛屿有一个权值V#xff0c;一条哈密顿路径C1#xff0c;C2#xff0c;...Cn的值为3部分之和#xff1a; 第1部分#xff0c;将路径中每个岛屿的权值累加起来#xff1b;第2部分#xff0c;对…http://poj.org/problem?id2288 题意 有n个岛屿每个岛屿有一个权值V一条哈密顿路径C1C2...Cn的值为3部分之和 第1部分将路径中每个岛屿的权值累加起来第2部分对路径中的每条边CiCi1将成绩Vi×Vi1累加起来第3部分当路径中连续的3个岛屿Ci、Ci1和Ci2形成一个三角形即在岛屿Ci和Ci2之间有一座桥则把乘积Vi×Vi1×Vi2累加起来。 寻找权值最大的哈密顿路径和其路径数。 思路 用d【status】【i】【j】表示当前状态为status并且最后两个顶点分别为 i 和 j 时的最大权值同理ways【status】【i】【j】表示此时对应的路径的数量。 1 #includeiostream2 #includealgorithm3 #includecstring4 #includecstdio5 #includesstream6 #includevector7 #includestack8 #includequeue9 #includecmath10 #includemap11 #includeset12 using namespace std;13 typedef long long ll;14 typedef pairint,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[113][13][13];23 ll ways[113][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 i0;in;i) scanf(%d,val[i]);38 for(int i0;im;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[(1u)|(1v)][u][v]d[(1u)|(1v)][v][u]val[u]val[v]val[u]*val[v];46 ways[(1u)|(1v)][u][v]ways[(1u)|(1v)][v][u]1;47 }48 49 ll maxvalue-1;50 ll maxways0;51 52 if(n1) {maxvalueval[0];maxways1;} //如果只有一个顶点则特判53 54 if(n!1)55 for(int s0;s(1n);s)56 {57 for(int i0;in;i)58 {59 if(s(1i))60 for(int j0;jn;j)61 {62 if((i!j) (s(1j)) d[s][i][j]-1)63 {64 for(int k0;kn;k) //枚举新加入的顶点65 {66 if(!(s(1k)) g[j][k])67 {68 int nextstatuss|(1k);69 ll tmp d[s][i][j]val[k]val[j]*val[k];70 if(g[i][k]) //如果Ci和Ci2之间存在桥71 tmpval[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(1n)-1;90 if(n!1)91 for(int i0;in;i)92 {93 for(int j0;jn;j)94 {95 if(g[i][j]0) continue;96 if(d[s][i][j]maxvalue)97 {98 maxvalued[s][i][j];99 maxwaysways[s][i][j];
100 }
101 else if(d[s][i][j]maxvalue)
102 maxwaysways[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 } 转载于:https://www.cnblogs.com/zyb993963526/p/7198529.html
