POJ 2288 Islands and Bridges （状压DP，变形）

题意：

　　给一个无向图，n个点m条边，每个点有点权，要求找到一条哈密顿路径，使得该路径的f(path)值最大。输出f值，若有多条最大f值的路径，输出路径数量。

　　f值由如下3点累加而来：

　　（1）所有点权之和。

　　（2）路径上相邻两点的点权之积。

　　（3）路径上如果有连续的3个点是一个三角形（即3点成环），则累加三点的点权之积。

思路：

　　根据f值的计算方式，第一项基本是不会变的，其他两项与路径有关。由于需要计算第3点，所以状态还需要记录每个状态的最后两个点（有序的），来判断是否为三角形。那么状态表示为[哪些点浏览过][倒数第2个点][末节点]，如果是在刚开始，只有1个点，那么第二维就是0就行了。路径数是根据DP的过程来计算的，开一个和状态数一样的数组保存即可。

　　注意点：路径统计要小心，图可能不连通，可能只有1个点，路径数可能爆LL？

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <deque>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 #define ULL unsigned long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 int n, w[N];

 LL cnt[<<][N][N], dp[<<][N][N],ans, ans2;

 bool g[N][N];

 void fuck(int s,int i,int k)

 {

     for(int j=; j<=n; j++) //枚举终点

     {

         if( (s&(<<j-)) || !g[i][j] )      continue;//已经走过or无路径

         LL c=cnt[s][k][i];

         LL v=dp[s][k][i]+w[i]*w[j];

         if( g[k][j] )  v+=w[k]*w[i]*w[j];    //三角形出现

         LL &cc=cnt[s|(<<j-)][i][j];

         LL &dd=dp[s|(<<j-)][i][j];

         if( dd<=v )

         {

             if(dd==v)    cc+=c;

             else         cc=c;

             dd=v;

         }

     }

 }

 void cal()

 {

     memset(dp,-,sizeof(dp));

     memset(cnt,,sizeof(cnt));

     ans=-;

     ans2=-;

     for(int i=; i<=n; i++)

     {

         dp[<<i-][][i]=;

         cnt[<<i-][][i]=;

     }

     for(int s=; s<(<<n); s++)

     {

         for(int i=; i<=n; i++)   //枚举k->i结尾

         {

             if( ( s&(<<i-) )== )   continue;

             for(int k=; k<=n; k++)

             {

                 if( k>&&(s&(<<k-))== || k==i ) continue;

                 if( dp[s][k][i]< )    continue;

                 fuck(s,i,k);

             }

         }

     }

     for(int i=; i<=n; i++)   //枚举k->i结尾

     {

         for(int k=; k<=n; k++)

         {

             if(i==k || dp[(<<n)-][k][i]< ) continue;

             if( ans==dp[(<<n)-][k][i] )

                 ans2+=cnt[(<<n)-][k][i];

             else if( ans<dp[(<<n)-][k][i] )

             {

                 ans=dp[(<<n)-][k][i];

                 ans2=cnt[(<<n)-][k][i];

             }

         }

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     int m, a, b, t, sum;cin>>t;

     while(t--)

     {

         sum=;

         scanf("%d%d",&n,&m);

         memset(g,,sizeof(g));

         for(int i=; i<=n; i++)

         {

             scanf("%d",&w[i]);

             sum+=w[i];

         }

         for(int i=; i<m; i++)

         {

             scanf("%d%d",&a,&b);

             g[a][b]=g[b][a]=true;

         }

         if(n==)    printf("%d 1\n", w[]);

         else

         {

             cal();

             if(ans<)    printf("0 0\n");

             else printf("%lld %lld\n", ans+sum, ans2/);

         }

     }

     return ;

 }

AC代码

巴特西

POJ 2288 Islands and Bridges （状压DP，变形）

最新文章

热门文章