poj 2288 Islands and Bridges

题目链接：http://poj.org/problem?id=2288

题目思路：TSP问题，不过要注意两个地方，n=1,路径数要用int64,悲剧啊，变量居然冲突了，害得我检查了一个小时;

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int t,n,m,st,ed,x;
int v[15],mp[15][15];
__int64 rec[1<<13][13][13];
int dp[1<<13][13][13];
int main()
{
    scanf("%d",&t);
    int i,j,k,l;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int sum=0;
        memset(mp,0,sizeof(mp));
        for(i=0;i<n;i++)
        {
            scanf("%d",&v[i]);
            sum+=v[i];
        }
        if(n==1)
        {
            printf("%d 1\n",v[0]);
            continue;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&ed,&st);
            mp[st-1][ed-1]=1;
            mp[ed-1][st-1]=1;
        }
       // memset(rec,0,sizeof(rec));
      //  memset(dp,-1,sizeof(dp));
        int tmp;
        for(i=0;i<(1<<n);i++)
            for(j=0;j<n;j++)
                for(k=0;k<n;k++)
                {
                    rec[i][j][k]=0;
                    dp[i][j][k]=-1;
                    if((i&(1<<j))!=0&&(i&(1<<k))!=0&&j!=k&&mp[j][k])
                    {
                        if(i-(1<<j)-(1<<k)==0)
                        {
                            dp[i][j][k]=v[j]*v[k];
                            rec[i][j][k]=1;
                          //  printf("i %d j %d k %d dp %d \n",i,j,k,dp[i][j][k]);
                            continue;
                        }
                        for(l=0;l<n;l++)
                        {
                             tmp=i-(1<<k);
                            if(l!=k&&l!=j&&(i&(1<<l))!=0&&dp[tmp][l][j]!=-1)
                            {
                                if(mp[l][k])
                                {
                                    x=dp[tmp][l][j]+v[j]*v[k]+v[l]*v[j]*v[k];
                                    if(x>dp[i][j][k])
                                    {
                                       rec[i][j][k]=rec[tmp][l][j];
                                       dp[i][j][k]=x;
                                    }
                                    else if(x==dp[i][j][k])
                                    {
                                        rec[i][j][k]+=rec[tmp][l][j];
                                    }
                                }
                                else
                                {
                                    x=dp[tmp][l][j]+v[j]*v[k];
                                    if(x>dp[i][j][k])
                                    {
                                        rec[i][j][k]=rec[tmp][l][j];
                                        dp[i][j][k]=x;
                                    }
                                    else if(x==dp[i][j][k])
                                    {
                                        rec[i][j][k]+=rec[tmp][l][j];
                                    }
                                }
                            }
                        }
                     //   printf("i %d j %d k %d dp %d rec %d\n",i,j,k,dp[i][j][k],rec[i][j][k]);
                    }
                }
                __int64 dfn=0;
                int ans=-1;
                for(i=0;i<n;i++)
                    for(j=0;j<n;j++)
                    {
                        if(i==j)
                            continue;
                        x=dp[(1<<n)-1][i][j];
                        if(ans<x)
                        {
                            ans=x;
                            dfn=rec[(1<<n)-1][i][j];
                        }
                        else if(ans==x)
                            dfn+=rec[(1<<n)-1][i][j];
                    }
                if(ans==-1)
                    printf("0 0\n");
                else
                printf("%d %I64d\n",ans+sum,dfn/2);
    }
}