题目描述

在 Byteland 有  个城市,并且其中有  个国王经常来访的主要城市。

其中有  条道路,每条道路连接两个城市。然而不幸的是,这些道路的环境极差使得国王无法全速驶过。

对于每条道路,翻修的成本是已知的。你的任务是选择性的翻修道路使得  个主要城市都可以经过翻修后的道路互相连通,且总成本尽量小。


 

裸的斯坦纳树

将指定点集合中的所有点连通,且边权总和最小的生成树称为最小斯坦纳树

令f[i][s]表示i号节点,联通性为s的最小代价

1.由子集转移

f[i][s]=min(f[i][s]+f[i][s^i])

枚举子集的方法

for(register int s=i&(i-1);s;s=i&(s-1));

2.由其他点转移

f[i][s]=min(f[x][s]+cost)

可以用死掉的spfa或者堆优化dij转移第二个

当然因为窝不会常数优化所以最少T一个点..

 


说点什么

avatar
  Subscribe  
提醒