NOIP 2017宝藏（状压DP）

70分做法:

全排列，再枚举这个点由那个点扩展出来的即可。

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxm=2007;
const int inf=1e9+7;
int dis[20][20];
int l[20],ans=1e9+7;//到i记录经过的点数 
int n,m;
void dfs(int sum,int num)
{
  if(sum>ans)
  return;
  if(num==n)
  ans=sum;
  for(int i=1;i<=n;i++)
  {
   if(l[i]) continue;
   for(int j=1;j<=n;j++)//枚举由哪个直接相连的点扩展过来 
   {
     if(!l[j]||i==j||dis[j][i]==inf) continue;
     int tmp=sum+l[j]*dis[j][i];
     l[i]=l[j]+1;
     dfs(tmp,num+1);
     l[i]=0;
   }
  }
}
int main()
{
 scanf("%d%d",&n,&m);
 memset(dis,inf,sizeof(dis));
 for(int i=1;i<=m;i++)
 {
   int x,y,z;
   scanf("%d%d%d",&x,&y,&z);
   if(dis[x][y]>z)dis[x][y]=dis[y][x]=z;
 }
 for(int i=1;i<=n;i++)
 {
  l[i]=1;
  dfs(0,1);
  l[i]=0;
 }
 printf("%d
",ans);
 return 0;	
}

满分做法:

(n<=12),考虑状压DP。首先我们会考虑到(dp[S])表示S状态下的代价，但因为本题的代价是动态的，所以不好转移。

但因为最后挖通的道路连成的图一定是一棵树，我们可以再加一维(dp[k][S]),表示第K层状态为(S)的代价，此时的层也就是深度，转移时把扩展的边权和乘(k-1)即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm=(1<<12)+7;
const int inf=1e9+7; 
ll dis[maxm][maxm];//dis[i][j]从i状态转移到j的最短路径总长 
ll dp[15][maxm];//dp[k][j] 到了第j层状态为j的代价
ll len[15][15];
int n,m;
int main()
{
 scanf("%d%d",&n,&m);
 memset(len,inf,sizeof(len));
 memset(dp,inf,sizeof(dp)); 
 for(int i=1;i<=m;i++)
 {
   int x,y,z;
   scanf("%d%d%d",&x,&y,&z);
   if(z<len[x][y])
   len[x][y]=len[y][x]=z;
 }
 for(int i=0;i<(1<<n);i++)
 {
  for(int j=i;j;j=(j-1)&i)//枚举i的子集
  {
   int bu=i^j;//j的补集
   bool flag=0;
   ll minn;
   for(int k=1;k<=n;k++)
   {
   	if((1<<(k-1))&bu)//哪个点还没有走过 
   	{
   	   minn=inf;
   	   for(int p=1;p<=n;p++)//寻找已经找过的点，能否向这个点扩展
	   {
	      if((1<<(p-1))&j)
		  minn=min(minn,len[p][k]);
	   }
	   if(minn==inf)
	   {
	   	 flag=1;
	   	 break;
	   }
	   dis[j][i]+=minn;
   	}
   }
   if(flag)
   dis[j][i]=inf;
  } 
 }
 for(int i=1;i<=n;i++)//根节点免费 
 dp[1][1<<(i-1)]=0;
 for(int k=2;k<=n;k++)
 {
  for(int i=0;i<(1<<n);i++)
  {
   for(int j=i;j;j=(j-1)&i)
   {
     if(dis[j][i]!=inf)
	 dp[k][i]=min(dp[k][i],dp[k-1][j]+(k-1)*dis[j][i]);	
   }
  }
 }
 ll ans=inf;
 for(int i=1;i<=n;i++)
 ans=min(ans,dp[i][(1<<n)-1]);
 printf("%lld
",ans);
 return 0;	
}