BZOJ_4006_[JLOI2015]管道连接_斯坦纳树
题意：
小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。
该部门有 n 个情报站，用 1 到 n 的整数编号。给出 m 对情报站 ui;vi 和费用 wi，表示情
报站 ui 和 vi 之间可以花费 wi 单位资源建立通道。
如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就
建立了通道连接。形式化地，若 ui 和 vi 建立了通道，那么它们建立了通道连接；若 ui 和 vi 均
与 ti 建立了通道连接，那么 ui 和 vi 也建立了通道连接。
现在在所有的情报站中，有 p 个重要情报站，其中每个情报站有一个特定的频道。小铭铭
面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。
分析：
先求一遍原图的斯坦纳树，处理出每个连通状态下的最小花费
但我们发现所求的方案并不一定是所有关键点都连通
再处理出每个频道需要情报站的状态
要进行状态之间的合并
DP g[i] = min(g[i], g[j] + g[i^j])
思路同BZOJ_4774
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1050
#define M 6050
int head[N],to[M],nxt[M],val[M],n,m,p,cnt,inq[N];
int dis[1025][N],Q[N],l,r,d[11],s[11];
int f[1025],g[1025],mask,tnl,is[11];
inline void add(int u,int v,int w){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;
}
struct A{
int id,num,rnum;
}b[11];
bool cmp1(const A &x,const A &y){
return x.rnum<y.rnum;
}
bool cmp2(const A &x,const A &y){
return x.id<y.id;
}
void stan(){
int i,j,k;
memset(dis,0x3f,sizeof(dis));
for(i=1;i<=p;i++){
dis[1<<i-1][d[i]]=0;
}
for(j=1;j<=mask;j++){
for(i=1;i<=n;i++){
for(k=j&(j-1);k;k=j&(k-1)){
dis[j][i]=min(dis[j][i],dis[k][i]+dis[j-k][i]);
}
}
l=r=0;
for(i=1;i<=n;i++){
Q[r++]=i;inq[i]=1;
}
while(l^r){
int x=Q[l++];inq[x]=0;if(l==n+1)l=0;
for(k=head[x];k;k=nxt[k]){
if(dis[j][to[k]]>dis[j][x]+val[k]){
dis[j][to[k]]=dis[j][x]+val[k];
if(!inq[to[k]]){
inq[to[k]]=1;Q[r++]=to[k];if(r==n+1)r=0;
}
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&p);
mask=(1<<p)-1;
int i,j,x,y,z,k;
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
for(i=1;i<=p;i++){
scanf("%d%d",&b[i].rnum,&d[i]);
b[i].id=i;
}
sort(b+1,b+p+1,cmp1);
b[0].rnum=-10000;
for(i=1;i<=p;i++){
if(b[i].rnum==b[i-1].rnum){
b[i].num=b[i-1].num;
}else b[i].num= ++tnl;
}
sort(b+1,b+p+1,cmp2);
for(i=1;i<=p;i++){
s[b[i].num]|=(1<<i-1);
}
stan();
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
for(i=0;i<=mask;i++){
for(j=1;j<=n;j++){
f[i]=min(f[i],dis[i][j]);
}
}
for(i=0;i<=mask;i++){
k=0;
for(j=1;j<=p;j++){
if(i&(1<<j-1)){
k|=s[b[j].num];
}
}
g[i]=f[k];
}
for(i=0;i<=mask;i++){
for(j=i&(i-1);j;j=i&(j-1)){
g[i]=min(g[i],g[j]+g[i-j]);
}
}
printf("%d\n",g[mask]);
}