首页 > 代码库 > 【Foreign】修路 [斯坦纳树]
【Foreign】修路 [斯坦纳树]
修路
Time Limit: 20 Sec Memory Limit: 256 MBDescription
Input
Output
仅一行一个整数表示答案。
Sample Input
5 5 2
1 3 4
3 5 2
2 3 1
3 4 4
2 4 3
Sample Output
9
HINT
Main idea
给定若干对点，选择若干边，询问满足每对点都连通的最小代价。
Source
发现 d 非常小，所以我们显然可以使用斯坦纳树来求解。
斯坦纳树是用来解决这种问题的：给定若干关键点，求使得关键点连通的最小代价。
我们可以令 f[i][opt] 表示以 i 为根时，关键点连通态为opt的最小代价。（以二进制表示是否连通）
然后我们就可以用两种方法来更新 f[i][opt]：
1. 设定集合x,y，x∪y=opt且x∩y=∅，那么我们显然就可以将用x,y合并来更新opt，
2. 若 f[j][opt] 中opt = f[i][opt]中opt，那么我们就可以以连边方式合并两个集合，这种合并方式显然可以用最短路实现，使得答案更优。
然后我们就可以求出所有状态的f[i][opt]，接下来再利用DP，求解。
定义Ans[opt]表示连通态为opt时最小代价，如果对应点同时连通或不连通则可以更新，枚举所有情况就可以求出答案了。
Code
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 using namespace std; 8 9 const int ONE = 20005; 10 const int MOD = 1e9+7; 11 12 int n,m,d; 13 int x,y,z; 14 int a[ONE]; 15 int next[ONE],first[ONE],go[ONE],w[ONE],tot; 16 int All,f[ONE/2][258],INF; 17 int q[10000005],vis[ONE],tou,wei; 18 int Ans[258]; 19 20 int get() 21 { 22 int res=1,Q=1; char c; 23 while( (c=getchar())<48 || c>57) 24 if(c==‘-‘)Q=-1; 25 if(Q) res=c-48; 26 while((c=getchar())>=48 && c<=57) 27 res=res*10+c-48; 28 return res*Q; 29 } 30 31 void Add(int u,int v,int z) 32 { 33 next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z; 34 next[++tot]=first[v]; first[v]=tot; go[tot]=u; w[tot]=z; 35 } 36 37 38 namespace Steiner 39 { 40 void pre() 41 { 42 memset(f,63,sizeof(f)); INF=f[0][0]; 43 int num = 0; 44 for(int i=1;i<=d;i++) f[i][1<<num] = 0, num++; 45 for(int i=n-d+1;i<=n;i++) f[i][1<<num] = 0, num++; 46 All = (1<<num) - 1; 47 } 48 49 void Spfa(int opt) 50 { 51 while(tou<wei) 52 { 53 int u=q[++tou]; 54 for(int e=first[u];e;e=next[e]) 55 { 56 int v=go[e]; 57 if(f[v][opt] > f[u][opt] + w[e]) 58 { 59 f[v][opt] = f[u][opt] + w[e]; 60 if(!vis[v]) 61 { 62 vis[v] = 1; 63 q[++wei] = v; 64 } 65 } 66 } 67 vis[u] = 0; 68 } 69 } 70 71 void Deal() 72 { 73 for(int opt=0;opt<=All;opt++) 74 { 75 for(int i=1;i<=n;i++) 76 { 77 for(int sub=opt;sub;sub=(sub-1) & opt) 78 f[i][opt] = min(f[i][opt],f[i][sub]+f[i][opt^sub]); 79 if(f[i][opt] != INF) 80 { 81 q[++wei] = i; 82 vis[i] = 1; 83 } 84 } 85 Spfa(opt); 86 } 87 } 88 } 89 90 bool Check(int opt) 91 { 92 for(int i=0,j=(d<<1)-1; i<d; i++,j--) 93 if( ((opt & (1<<i))== 0) != ((opt & (1<<j))==0) ) 94 return 0; 95 return 1; 96 } 97 98 int main() 99 {100 n=get(); m=get(); d=get();101 for(int i=1;i<=m;i++)102 {103 x=get(); y=get(); z=get();104 Add(x,y,z);105 }106 107 Steiner::pre();108 Steiner::Deal();109 110 memset(Ans,63,sizeof(Ans));111 for(int opt=0;opt<=All;opt++)112 if(Check(opt))113 {114 for(int i=1;i<=n;i++)115 Ans[opt] = min(Ans[opt], f[i][opt]);116 }117 118 for(int opt=0;opt<=All;opt++)119 for(int sub=opt;sub;sub=(sub-1) & opt)120 Ans[opt] = min(Ans[opt], Ans[sub]+Ans[opt^sub]);121 122 if(Ans[All] == INF) printf("-1");123 else printf("%d",Ans[All]);124 }
【Foreign】修路 [斯坦纳树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。