【题目链接】
http://acm.hdu.edu.cn/showproblem.php?pid=3311
【题意】
给定k座庙，n个其他点，m条边，点权代表挖井费用，边权代表连边费用，问使得k座庙里的所有和尚都能吃到水的最小费用。
【思路】
首先一个相连的块里只要有口井就能保证块里的和尚有水。所以这个题目标并不是要让k个点连通，但我们可以转化一下。
在原图的基础上我们添加0号结点，由0号结点向所有的点连边为该点的点权，代表挖井的费用，从而保证每个块里都有井，则问题转化为求以0为根包含k个点的斯坦纳树。
模板可以上了。
奇技淫巧系列。。。
【代码】
1 #include<set> 2 #include<cmath> 3 #include<queue> 4 #include<vector> 5 #include<cstdio> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt) 10 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 11 using namespace std; 12 13 typedef long long ll; 14 const int N = 1e3+10; 15 const int M = 2e4+10; 16 const int inf = 0xf0f0f0f; 17 const int P = 10; 18 19 ll read() { 20 char c=getchar(); 21 ll f=1,x=0; 22 while(!isdigit(c)) { 23 if(c=='-') f=-1; c=getchar(); 24 } 25 while(isdigit(c)) 26 x=x*10+c-'0',c=getchar(); 27 return x*f; 28 } 29 struct Edge { int v,w,nxt; 30 }e[M]; 31 int en=1,front[N]; 32 void adde(int u,int v,int w) 33 { 34 e[++en]=(Edge){v,w,front[u]}; front[u]=en; 35 } 36 37 int n,m,K; 38 int f[1<<P][N]; 39 queue<int> q; int inq[N]; 40 41 void spfa(int* dis) 42 { 43 while(!q.empty()) { 44 int u=q.front(); q.pop(); 45 inq[u]=0; 46 trav(u,i) { 47 int v=e[i].v; 48 if(dis[v]>dis[u]+e[i].w) { 49 dis[v]=dis[u]+e[i].w; 50 if(!inq[v]) 51 inq[v]=1,q.push(v); 52 } 53 } 54 } 55 } 56 57 int main() 58 { 59 while(scanf("%d%d%d",&K,&n,&m)==3) { 60 en=1; 61 memset(front,0,sizeof(front)); 62 int rt=0; 63 n+=K; 64 FOR(i,1,n) { 65 int w=read(); 66 adde(rt,i,w),adde(i,rt,w); 67 } 68 FOR(i,1,m) { 69 int u=read(),v=read(),w=read(); 70 adde(u,v,w),adde(v,u,w); 71 } 72 memset(f,0xf,sizeof(f)); 73 FOR(i,0,K) f[1<<i][i]=0; 74 int all=1<<(K+1); 75 FOR(st,1,all-1) { 76 FOR(i,0,n) { 77 for(int s=st&(st-1);s;s=(s-1)&st) 78 f[st][i]=min(f[st][i],f[s][i]+f[st^s][i]); 79 if(f[st][i]!=inf) q.push(i),inq[i]=1; 80 } 81 spfa(f[st]); 82 } 83 printf("%d ",f[all-1][rt]); 84 } 85 return 0; 86 }