【BZOJ3590】[Snoi2013]Quare 狀壓DP

題解：

一道比較水的題

但這個測試數據極弱我也不知道我的代碼正確性是不是有保證

構成一個邊雙聯通

可以由兩個有一個公共點的邊雙聯通或者一個邊雙加一條鏈構成

所以我們需要要預處理出所有環

令f[i][j][k]表示起點為i，終點為j，經過點的狀態為k,這樣遞推

那么最后環就是加上j-i這條邊就可以了

但是注意一個二元環，一個為最長邊一個為次長邊

其他環都不會用到次長邊

代碼：

#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rint register int
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define rep(i,h,t) for (rint i=h;i<=t;i++)
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);while(c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; 
}
void umin(int &x,int y)
{if (x>y) x=y;
}
int dp[15][15][1<<14],ff[1<<14],f[20][20][2],n,m;
bool tf[1<<14];
const int INF=1e9;
int main()
{int T;read(T);rep(tt,1,T){read(n); read(m);rep(i,1,n) rep(j,1,n)f[i][j][0]=f[i][j][1]=INF;rep(i,1,m){int x,y,z;read(x); read(y); read(z);if (z<=f[x][y][0]) f[x][y][1]=f[x][y][0],f[x][y][0]=z,f[y][x][1]=f[y][x][0],f[y][x][0]=z;else if (z<f[x][y][1]) f[x][y][1]=z,f[y][x][1]=z;}rep(i,1,n)rep(j,1,n)rep(k,1,(1<<n)-1) dp[i][j][k]=INF;rep(i,1,n) dp[i][i][(1<<(i-1))]=0;rep(i,1,(1<<n)-1){int a[100];int cnt=0;rep(j,1,n)if ((i>>(j-1))&1) a[++cnt]=j;rep(i1,1,cnt)rep(j1,1,cnt)rep(k,1,n)if (!((i>>(k-1))&1))umin(dp[a[i1]][k][i|(1<<(k-1))],dp[a[i1]][a[j1]][i]+f[a[j1]][k][0]);}rep(i,1,(1<<n)-1) tf[i]=0;rep(i,1,(1<<n)-1) ff[i]=INF;rep(i,1,n)rep(j,1,n)if (i!=j)tf[(1<<(i-1))+(1<<(j-1))]=1,ff[(1<<(i-1))+(1<<(j-1))]=min(INF,f[i][j][0]+f[i][j][1]);rep(i,1,(1<<n)-1)if (!tf[i])rep(j,1,n)rep(k,1,n)umin(ff[i],dp[j][k][i]+f[j][k][0]);rep(i,1,(1<<n)-1)for (int j=i;j;j=i&(j-1))rep(k,1,n)if (j&(1<<(k-1)))umin(ff[i],ff[(i^j)|(1<<(k-1))]+ff[j]);if (ff[(1<<n)-1]!=INF) cout<<ff[(1<<n)-1]<<endl;else cout<<"impossible"<<endl; }return 0; 
}

?