斯坦纳树有什么用

个人一点粗浅理解……

最基本形式的斯坦纳树问题（以下简称母问题）：给定图G和一个关键点集V。求在G中选取一个权值最小（这里权值可以有很多变式）的边集E使V中的点两两连通。

由于这个母问题只对关键点有限制。那么可以用状压dp的做法：$f[i][j]$表示对于$i$点而言，它已连通的关键点状态为$j$的最小代价。

那么$f[i][j]$就有两种转移方式：1.从$f[i][t]$转移而来；2.从$f[v][j]$转移而来。

注意到第一种转移就相当于枚举子集；第二种转移形如最短路问题。那么只需要每次额外对于第二种转移做一遍最短路即可。

最终的时间复杂度为$O(n*3^k)$。

【dp套斯坦纳树】bzoj4774: 修路

Description

村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)，

请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边

的权值和。

Input

第一行三个整数 n, m，d,表示图的点数和边数。接下来的 m行，每行三个整数 ui, vi, wi，表示有一条 ui 与 vi

之间，权值为 wi 的无向边。

1 <= d <= 4

2d <= n <= 10^4

0 <= m <= 10^4

1 <= ui, vi <= n

1 <= wi <= 1000

Output

一行一个整数，表示答案，如果无解输出-1

题目分析

不同的是，这里只要求$i$和$n-i+1$连通。

用$f[i][j]$表示对于$i$节点，$2d$个点的连通状态为$j$时的最小代价。另用$g[t]$表示全局$t$状态时的最小代价。

若$t$状态可拆成$x,y$两个合法状态，$g[x]+g[y]$也可以用于更新$g[t]$状态。

 1 #include<bits/stdc++.h>
 2 const int maxn = 10035;
 3 const int maxm = 20035;
 4 const int INF = 0x3f3f3f3f;
 5 
 6 struct Edge
 7 {
 8     int y,val;
 9     Edge(int a=0, int b=0):y(a),val(b) {}
10 }edges[maxm];
11 int n,m,d;
12 bool vis[maxn];
13 std::queue<int> q;
14 int f[maxn][305],g[305];
15 int edgeTot,head[maxn],nxt[maxm];
16 
17 int read()
18 {
19     char ch = getchar();
20     int num = 0;
21     bool fl = 0;
22     for (; !isdigit(ch); ch=getchar())
23         if (ch=='-') fl = 1;
24     for (; isdigit(ch); ch=getchar())
25         num = (num<<1)+(num<<3)+ch-48;
26     if (fl) num = -num;
27     return num;
28 }
29 void spfa(int st)
30 {
31     for (int i=1; i<=n; i++)
32         if (f[i][st]!=INF) q.push(i);
33     while (q.size())
34     {
35         int tt = q.front();
36         q.pop(), vis[tt] = 0;
37         for (int i=head[tt]; i!=-1; i=nxt[i])
38         {
39             int v = edges[i].y, w = edges[i].val;
40             if (f[v][st] > f[tt][st]+w){
41                 f[v][st] = f[tt][st]+w;
42                 if (!vis[v]) vis[v] = 1, q.push(v);
43             }
44         }
45     }
46 }
47 bool check(int num)
48 {
49     for (int i=0; i<d; i++)
50         if (((num>>i)&1)&&((num>>(d+i))&1)==0) return 0;
51     return 1;
52 }
53 void addedge(int u, int v)
54 {
55     int c = read();
56     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;
57     edges[++edgeTot] = Edge(u, c), nxt[edgeTot] = head[v], head[v] = edgeTot;
58 }
59 int main()
60 {
61     memset(head, -1, sizeof head);
62     memset(f, 0x3f3f3f3f, sizeof f);
63     memset(g, 0x3f3f3f3f, sizeof g);
64     n = read(), m = read(), d = read();
65     for (int i=1; i<=m; i++) addedge(read(), read());
66     for (int i=1; i<=d; i++)
67         f[i][1<<(i-1)] = 0, f[n-i+1][1<<(d+i-1)] = 0;
68     for (int i=0; i<1<<(d<<1); i++)
69     {
70         for (int j=1; j<=n; j++)
71             for (int s=i&(i-1); s; s=(s-1)&i)
72                 f[j][i] = std::min(f[j][i], f[j][s]+f[j][i-s]);
73         spfa(i);
74         for (int j=1; j<=n; j++) g[i] = std::min(g[i], f[j][i]);
75     }
76     for (int i=0; i<1<<(d<<1); i++)
77         for (int s=i&(i-1); s; s=(s-1)&i)
78             if (check(s)&&check(i-s))
79                 g[i] = std::min(g[i], g[s]+g[i-s]);
80     if (g[(1<<(d<<1))-1] != INF)
81         printf("%d
",g[(1<<(d<<1))-1]);
82     else puts("-1");
83     return 0;
84 }

END