给一张图 要求 对于(i<=d)号点要和(n-i+1)号点相连 问最小化选出的边的和。
裸斯坦纳树 考虑一个dp f[i][j]表示当前集合i被联通且在j号点的方案数。
可以发现这个状态可以传递到 k号点 这个可以通过最短路的形式传递。
考虑状态合并 发现最优决策中是一个点联通多个关键点 所以对一个状态s来说 必然由某个点联通 枚举子集转移即可。
发现最后是要求两两点联通 可以不全部联通。
设g[i]表示状态为i的最小代价 可以发现 g[i]的下界为min{f[i][j]}
考虑可能两个点是单独联通的 所以枚举转移 再dp一遍即可。
值得注意的是 (d<=4,n,mleq 10000)不开o2 1.5s 而我们的复杂度为3^8n+2^8mlogn.
这个时限在卡dij的堆的常数 稀疏图spfa跑的更快 这点不要忘记. 所以采用spfa的玄学复杂度.
const int MAXN=10010;
int n,m,dd,len,maxx,top,l,r;
int id[MAXN],vis[MAXN],v[MAXN];
int f[1<<9][MAXN],g[1<<9];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],e[MAXN<<1],q[MAXN*20];
inline void add(int x,int y,int z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z;
}
inline void dij(int s)
{
while(++l<=r)
{
int x=q[l];vis[x]=0;
go(x)
{
if(f[s][tn]>f[s][x]+e[i])
{
f[s][tn]=f[s][x]+e[i];
if(!vis[tn])q[++r]=tn,vis[tn]=1;
}
}
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);get(dd);
rep(1,m,i)
{
int get(x);int get(y);int get(z);
add(x,y,z);add(y,x,z);
}
rep(1,dd,i)id[i]=i,id[dd+i]=n-dd+i;
dd=dd<<1;maxx=(1<<dd)-1;
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
rep(1,dd,i)f[(1<<(i-1))][id[i]]=0;
rep(1,maxx,i)
{
l=r=0;
rep(1,n,j)
{
for(int s=i;s;s=i&(s-1))f[i][j]=min(f[i][j],f[s][j]+f[s^i][j]);
if(f[i][j]<INF)q[++r]=j,vis[j]=1;
g[i]=min(g[i],f[i][j]);
}
dij(i);
}
rep(1,dd/2,i)v[i]=(1<<(i-1))|(1<<(dd-i));
rep(1,maxx,i)rep(1,dd/2,j)if((i&v[j])==v[j])g[i]=min(g[i],g[i^v[j]]+g[v[j]]);
put(g[maxx]>INF?-1:g[maxx]);return 0;
}