本场考试最有意义的一道题，思路根据题解和 ICEY 钻研了好久但最后分道扬镳了，写篇题解纪念一下。
先构造出最终状态，最后的状态一定是 \(1\) 到 \(n\) 的一条链,并且不在链上的每个联通块最多只和链上的一个点有连边。 形如：

我们定义状态：
\(dp_{u,s}\) 为当前链的末端点为 \(u\)，已联通的点的集合为 \(s\) 。
当转移到 \(u\) 点时，有两种选择方案，

1.不添加枝叶，添加链。

2.添加枝叶，不添加链。

枝叶就是联通块，对于每个点的可行性枝叶可以预处理出来，同时注意添加的联通块不能包含 \(n\) 节点，因为 \(n\) 一定在链上。另外根据最终状态的的定义，新添加的联通块不能包含已联通的点。

先说一下预处理，
先把每个联通块状态的权值更新

	for(re int s=1;s<(1<<n);s++) {
		for(re int i=1;i<=n;i++) if(s&(1<<i-1)) {
			for(re int j=head[i],to;j;j=edge[j].nxt) {
				to=edge[j].var;
				if((to>i)&&(s&(1<<to-1))) cses[s]+=edge[j].cst;
			} 
		} 
	} 

下面是把每个点所能达到的联通块状态处理出来

	for(re int i=1,lim;i<=n;i++) {
		lim=(1<<i-1);
		vis[i][lim]=1;
		for(re int s=lim;s<(1<<n);s++) if(vis[i][s]) {
			for(re int j=1;j<=n;j++) if(!(s&(1<<j-1))&&(ds[j]&s)) {
				if(!vis[i][s|(1<<j-1)]) {
					if(i==n) zi[i][++zi[i][0]]=s|(1<<j-1);
					else if(!((s|(1<<j-1))&(1<<n-1))) zi[i][++zi[i][0]]=s|(1<<j-1);
					vis[i][s|(1<<j-1)]=1;
				}
			} 
		} 
	} 

转移就很好说了，分情况转移

	dp[1][1]=1;
	int lim=(1<<(n-1));
	for(re int sum_tmp=1;sum_tmp<lim;sum_tmp++) 
	for(re int now=1;now<n;now++) if(dp[now][sum_tmp]) {  
		for(re int i=1,tmp;i<=zi[now][0];i++)  {   // Situation 1
			tmp=zi[now][i];
			if((tmp&(sum_tmp^(1<<now-1)))) continue;
			dp[now][sum_tmp|tmp]=max(dp[now][sum_tmp|tmp],dp[now][sum_tmp]+cses[tmp]);
		}
		for(re int i=head[now],to;i;i=edge[i].nxt) {    // Situation 2 
			to=edge[i].var;
			if((sum_tmp&(1<<to-1))) continue;
			dp[to][sum_tmp|(1<<to-1)]=max(dp[to][sum_tmp|(1<<to-1)],dp[now][sum_tmp]+edge[i].cst);
		}
	}

注意最后的答案更新，\(n\) 点还要分情况讨论一下

Code

#include <bits/stdc++.h>
#define re register
#define db double
#define pir make_pair
#define max(x,y) (x)>(y)? (x):(y)
using namespace std; 
const int maxn=16;
const int INF=1e9;

inline int read() {
   int s=0,w=1; char ch=getchar();
   while(ch<'0'||ch>'9') { if(ch=='-') w=-1;ch=getchar(); }
   while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar(); }
   return s*w;
}
struct EDGE { int var,cst,nxt; } edge[(maxn*maxn)<<1];
int n,m,head[maxn],cnt,cses[1<<maxn],ans,res;
bool vis[maxn][1<<maxn];int ds[maxn];
inline void add(int a,int b,int c) { edge[++cnt]=(EDGE){ b,c,head[a] }; head[a]=cnt; }
int zi[maxn][1000010];
int dp[maxn][1<<maxn];
signed main(void) {
   //freopen("connect4.in","r",stdin);
   n=read(),m=read();
   for(re int i=1,u,e,w;i<=m;i++) {
   	u=read(),e=read(),w=read();
   	res+=w;
   	ds[u]|=(1<<e-1); ds[e]|=(1<<u-1);
   	add(u,e,w); add(e,u,w);
   }
   for(re int s=1;s<(1<<n);s++) {
   	for(re int i=1;i<=n;i++) if(s&(1<<i-1)) {
   		for(re int j=head[i],to;j;j=edge[j].nxt) {
   			to=edge[j].var;
   			if((to>i)&&(s&(1<<to-1))) cses[s]+=edge[j].cst;
   		} 
   	} 
   } 
   for(re int i=1,lim;i<=n;i++) {
   	lim=(1<<i-1);
   	vis[i][lim]=1;
   	for(re int s=lim;s<(1<<n);s++) if(vis[i][s]) {
   		for(re int j=1;j<=n;j++) if(!(s&(1<<j-1))&&(ds[j]&s)) {
   			if(!vis[i][s|(1<<j-1)]) {
   				if(i==n) zi[i][++zi[i][0]]=s|(1<<j-1);
   				else if(!((s|(1<<j-1))&(1<<n-1))) zi[i][++zi[i][0]]=s|(1<<j-1);
   				vis[i][s|(1<<j-1)]=1;
   			}
   		} 
   	} 
   } 
   dp[1][1]=1;
   int lim=(1<<(n-1));
   for(re int sum_tmp=1;sum_tmp<lim;sum_tmp++) 
   for(re int now=1;now<n;now++) if(dp[now][sum_tmp]) {
   	for(re int i=1,tmp;i<=zi[now][0];i++)  {
   		tmp=zi[now][i];
   		if((tmp&(sum_tmp^(1<<now-1)))) continue;
   		dp[now][sum_tmp|tmp]=max(dp[now][sum_tmp|tmp],dp[now][sum_tmp]+cses[tmp]);
   	}
   	for(re int i=head[now],to;i;i=edge[i].nxt) {
   		to=edge[i].var;
   		if((sum_tmp&(1<<to-1))) continue;
   		dp[to][sum_tmp|(1<<to-1)]=max(dp[to][sum_tmp|(1<<to-1)],dp[now][sum_tmp]+edge[i].cst);
   	}
   }
   for(re int s=1;s<(1<<n);s++) if(dp[n][s]) {
   	int ls=0;
   		for(re int i=1,tmp;i<=zi[n][0];i++) {
   			tmp=zi[n][i];
   			if((tmp&(s^(1<<n-1)))) continue;
   			ls=max(ls,cses[tmp]);
   		}
   	ans=max(ans,ls+dp[n][s]); 
   }
   printf("%d\n",res-ans+1);
}

奠死掉的dfs... 深搜比循环慢，因为这个被T飞了

inline void dfs(int now,int sum_tmp,int val) {
	//if(v[pir(pir(now,sum_tmp),val)]) return;
	//v[pir(pir(now,sum_tmp),val)]=1;
	//if(v[pir(now,sum_tmp)]>val) return;
	//v[pir(now,sum_tmp)]=val;
	if(dp[now][sum_tmp]>val) return;
	dp[now][sum_tmp]=val;
	if(now==n) { 
		int ls=0;
		for(re int i=1,tmp;i<=zi[now][0];i++) {
			tmp=zi[now][i];
			if((tmp&(sum_tmp^(1<<now-1)))) continue;
			ls=max(ls,cses[tmp]);
		}
		//cout<<ans<<endl; 
		ans=max(ans,ls+val); 
		return; 
	}
	for(re int i=head[now],to;i;i=edge[i].nxt) {
		to=edge[i].var;
		if((sum_tmp&(1<<to-1))) continue;
		dfs(to,sum_tmp|(1<<to-1),val+edge[i].cst);
	}
	for(re int i=1,tmp;i<=zi[now][0];i++)  {
		tmp=zi[now][i];
		if((tmp&(sum_tmp^(1<<now-1)))||(tmp&(1<<n-1))) continue;
		dfs(now,sum_tmp|tmp,val+cses[tmp]);
	}
	
}

考试总结： 动态开点注意空间，能 \(DP\) 不深搜。