POJ

比较裸的状压，cnt没开 long long WA到死。。。还要注意一下n为1的情况。
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define fi first
  5 #define se second
  6 #define mk make_pair
  7 #define pii pair<int,int>
  8 #define read(x) scanf("%d",&x)
  9 #define sread(x) scanf("%s",x)
 10 #define dread(x) scanf("%lf",&x)
 11 #define lread(x) scanf("%lld",&x)
 12 using namespace std;
 13 
 14 typedef long long ll;
 15 const int inf=0x3f3f3f3f;
 16 const int INF=0x3f3f3f3f3f3f3f3f;
 17 const int N=13;
 18 const int M=10;
 19 const int mod=1e9+7;
 20 
 21 int n,m,up,a[N],d[N][N];
 22 ll dp[N][N][1<<N],cnt[N][N][1<<N],mx;
 23 void init()
 24 {
 25     memset(dp,-1,sizeof(dp));
 26     memset(d,false,sizeof(d));
 27     memset(cnt,0,sizeof(cnt));
 28     mx=-INF;
 29 }
 30 int main()
 31 {
 32     int T; read(T);
 33     while(T--)
 34     {
 35         init();
 36 
 37         read(n); read(m);
 38         for(int i=0;i<n;i++)
 39             read(a[i]);
 40         for(int i=1;i<=m;i++)
 41         {
 42             int u,v;
 43             read(u); read(v);
 44             u--; v--;
 45             d[u][v]=true;
 46             d[v][u]=true;
 47         }
 48         if(n==1)
 49         {
 50             printf("%d 1
",a[0]);
 51             continue;
 52         }
 53         for(int i=0;i<n;i++)
 54             for(int j=0;j<n;j++)
 55                 if(i!=j && d[i][j])
 56                     dp[i][j][(1<<i)|(1<<j)]=a[i]*a[j]+a[i]+a[j], cnt[i][j][(1<<i)|(1<<j)]=1;
 57 
 58         up=1<<n;
 59         for(int s=0;s<up;s++)
 60         {
 61             for(int i=0;i<n;i++)
 62             {
 63                 for(int j=0;j<n;j++)
 64                 {
 65                     if(dp[i][j][s]==-1)
 66                         continue;
 67                     if(s==up-1)
 68                         mx=max(mx,dp[i][j][s]);
 69                     for(int k=0;k<n;k++)
 70                     {
 71                         if(!d[j][k] || s&(1<<k))
 72                             continue;
 73                         ll ret=dp[i][j][s]+a[j]*a[k]+a[k];
 74                         if(d[i][j] && d[i][k] && d[j][k])
 75                             ret+=a[i]*a[j]*a[k];
 76                         if(ret>dp[j][k][s|(1<<k)])
 77                         {
 78                             cnt[j][k][s|(1<<k)]=cnt[i][j][s];
 79                             dp[j][k][s|(1<<k)]=ret;
 80                         }
 81                         else if (ret==dp[j][k][s|(1<<k)])
 82                             cnt[j][k][s|(1<<k)]+=cnt[i][j][s];
 83                     }
 84                 }
 85             }
 86         }
 87         if(mx==-INF)
 88             puts("0 0");
 89         else
 90         {
 91             ll tot=0;
 92             for(int i=0;i<n;i++)
 93                 for(int j=0;j<n;j++)
 94                     if(dp[i][j][up-1]==mx)
 95                         tot+=cnt[i][j][up-1];
 96             printf("%lld %lld
",mx,tot/2);
 97         }
 98 
 99     }
100     return 0;
101 }
102 /*
103 */