hdu3001（三进制状压）

题目大意：

现在给你一个有n个点和m条边的图，每一条边都有一个费用，每个点不能经过超过两次，求所有点至少遍历一次的最小费用

其中n<=10 m没有明确限制（肯定不会超过1e5)

一看到这个数据范围，第一想法就是状压QWQ

但是转念一想，woc，每个点不一定只经过一次咯。

woc，那不就是三进制状压？！

好的，至此，这个题成功的成为了我人生中的第一道三进制状压

f[S][i]表示已经走过的点的集合是S 当前在i的最小费用

首先，我们要先预处理一个num数组

num[i][j]表示i这个数的三进制拆分的第j位是什么

void count()
{
    for (int i=0;i<=59049;i++)
    {
        int cnt=i;
        for (int j=1;j<=10;j++)
          num[i][j]=cnt%3,cnt/=3;
    }
}

便于之后的计算

之后枚举状态

枚举当前点，枚举目标点，进行转移即可

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
   while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
   return x*f;
}

int f[100010][12];
int num[100010][12];
int n,m;
int a[20][20];
int ymh;
bool pp;

int qsm(int i,int j)
{
    int ans=1;
    while (j)
    {
        if (j&1) ans*=i;
        i=i*i;
        j>>=1;
    }
    return ans;
}

void init()
{
    memset(f,127/3,sizeof(f));
    memset(a,-1,sizeof(a));
}

void count()
{
    for (int i=0;i<=59049;i++)
    {
        int cnt=i;
        for (int j=1;j<=10;j++)
          num[i][j]=cnt%3,cnt/=3;
    }
}

int main()
{
  count();
  while (scanf("%d%d",&n,&m)!=EOF){
      init();
      int ans=1e9;
      pp=true;      
    for (int i=1;i<=m;i++)
      {
          int u,v,w;
          u=read();v=read();w=read();
          if (a[u][v]==-1){
              a[u][v]=w;
          }
          else a[u][v]=min(a[u][v],w);
          a[v][u]=a[u][v];
      }
      ymh=qsm(3,n)-1;
      //cout<<ymh<<endl;
      for (int i=1;i<=n;i++)
        f[qsm(3,i-1)][i]=0;
      for (int i=1;i<=ymh;i++)
      {
          bool flag=true;
          for (int j=1;j<=n;j++)
          {
              if (num[i][j]==0)
              {
                  flag=false;
                  continue;
              }
              for (int k=1;k<=n;k++)
              {
                  if (a[j][k]!=-1 && num[i][k]<2 && k!=j)
                  {
                      int kk=i+qsm(3,k-1);
                      f[kk][k]=min(f[kk][k],f[i][j]+a[j][k]);
                  }
              }
          }
        if (flag)
          for (int j=1;j<=n;j++)
           ans=min(ans,f[i][j]);
      }
    if (ans==f[100001][11]) ans=-1;
      cout<<ans<<endl;
  }
  return 0;
}