luogu P5776 [SNOI2013]Quare

题面传送门
首先我们考虑一个两个已经是点双的点集怎么合并。
显然是找到两条最小的且跨立的边连起来对吧。
但是你会发现其实不用两个都是点双，其中一个是，另一个只要是链，然后那两条边连两个端点即可。
所以可以先一遍做出\(f_{i,x,y}\)表示\(i\)点集构成的链，\(x,y\)为端点的最小值。
然后再dp出\(g_{i}\)表示\(i\)集合的点构成点双的最小值。直接暴力枚举子集就好了。
时间复杂度大概是\(O(n^32^n+n^23^n)\)，跑得挺快的。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N ((1<<12)+5)
#define M (40+5)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n,m,k,T,dp[N][15][15],F[N],x,y,z,G[20][N],W1[20][20],W2[20][20];
I int calc(int x,int y){int Ans=1e9;for(RI i=1;i<=n;i++) y>>(i-1)&1&&(Ans=min(Ans,W1[x][i]));return Ans;}
I void ADD(int w){x>w?(y=x,x=w):(y=min(y,w));}
I int CK(int a,int b){x=y=1e9;for(RI i=1;i<=n;i++) b>>(i-1)&1&&(ADD(W1[a][i]),ADD(W2[a][i]),0);return x+y;}
I void Solve(){
	RI i,j,h,k;Me(W1,0x1f);Me(W2,0x1f);Me(dp,0x1f);Me(F,0x1f);scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),W1[x][y]>z?(W2[x][y]=W2[y][x]=W1[x][y],W1[x][y]=W1[y][x]=z):(W2[x][y]=W2[y][x]=min(W2[x][y],z));
	for(i=1;i<=n;i++) dp[1<>(j-1)&1)) continue;
			for(h=1;h<=n;h++){if(j==h||!(i>>(h-1)&1)) continue;
				for(k=1;k<=n;k++) {if(!(i>>k-1)&1) continue;
					if(k^j) dp[i][j][h]=min(dp[i^(1<>(h-1)&1)) continue;G[i][j]=min(G[i][j^(1<>(k-1)&1)) continue;
				for(h=k;h<=n;h++){if(!(j>>(h-1)&1)) continue;
					if(j==(1<1e8) puts("impossible");
	else printf("%d\n",F[(1<