首页 > 代码库 > poj 2288 Islands and Bridges

poj 2288 Islands and Bridges

2024-07-13 02:08:08   219人阅读

题意： 给你一个双向连通图，求 获得权值最大 的 哈密顿通路的 权值 和 这个权值对应的数目；

　　其中权值计算方法是  列如 ABCD  权值是a+b+c+d+ab+bc+cd 如果 A,B,C  和B，C，D 可构成三角形分别加上abc，bcd；

这个题 和poj 3311  很相像： 那个需要记录一个最后到达的地方   这个需要记录俩个罢了

DP[i][a][b]其中 i  二进制 中1表示这个点走过了   最后走的的 的是b>>a

因为对于已经走过了{1，2，3，4，,5，6，..,N}　　为了推出下一次走到X 我们要获得权值 只和最后走的俩个点有关？

给出代码：：

 1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstdlib> 5 #include <cstring> 6 #include <iostream> 7 using namespace std; 8 long long  dp[1<<13][13][13]; 9 long long  num[1<<13][13][13];10 int n;11 int val[13];12 bool Map[13][13];13 void solve()14 {15     for(int i=0;i<(1<<n);i++)for(int a=0;a<n;a++)for(int b=0;b<n;b++)16     {17         if(!Map[a][b])continue;18         if(a==b)continue;19         if((i&(1<<a))==0||(i&(1<<b))==0)continue;20         if(i==((1<<a)+(1<<b)))21         {22             dp[i][a][b]=val[a]+val[b]+val[a]*val[b];23             num[i][a][b]=1;24             continue;25         }26         else27         {28             for(int c=0;c<n;c++)29             {30                 if(c==a||c==b||(!Map[b][c])) continue;31                 if((i&(1<<c))==0) continue;32                 long long  tmp;33                 if(dp[i^(1<<a)][b][c]==-1)continue;34                 if(Map[a][c]) tmp=val[a]+val[a]*val[b]+val[a]*val[b]*val[c];35                 else tmp=val[a]+val[a]*val[b];36                 if(dp[i][a][b]<dp[i^(1<<a)][b][c]+tmp)37                 {38                     num[i][a][b]=num[i^(1<<a)][b][c];39                     dp[i][a][b]=dp[i^(1<<a)][b][c]+tmp;40                 }41                 else if(dp[i][a][b]==dp[i^(1<<a)][b][c]+tmp)42                     num[i][a][b]+=num[i^(1<<a)][b][c];43             }44         }45     }46     long long  ans=-1;47     long long  ans_num=0;48     for(int b=0;b<n;b++) for(int c=0;c<n;c++)49     {50         if(ans<dp[(1<<n)-1][b][c])51         {52             ans=dp[(1<<n)-1][b][c];53             ans_num=num[(1<<n)-1][b][c];54         }55         else if(ans==dp[(1<<n)-1][b][c])56             ans_num+=num[(1<<n)-1][b][c];57 58     }59     if(ans==-1) printf("0 0\n");60     else printf("%lld %lld\n",ans,ans_num/2);61 }62 int main()63 {64     int q;65     scanf("%d",&q);66     while(q--)67     {68         memset(Map,false,sizeof(Map));69         memset(dp,-1,sizeof(dp));70         memset(num,0,sizeof(num));71         int m;72         scanf("%d%d",&n,&m);73         for(int i=0;i<n;i++)scanf("%d",&val[i]);74         for(int i=1;i<=m;i++)75         {76             int a,b;77             scanf("%d%d",&a,&b);78             a--,b--;79             Map[a][b]=Map[b][a]=true;80         }81         if(n==1) printf("%d 1\n",val[0]);82         else83         solve();84     }85     return 0;86 }


联系
我们