斯坦纳树的基础应用

斯坦纳树有什么用

个人一点粗浅理解……

最基本形式的斯坦纳树问题（以下简称母问题）：给定图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]$状态。

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 const int INF = 0x3f3f3f3f;

 struct Edge

 {

     int y,val;

     Edge(int a=, int b=):y(a),val(b) {}

 }edges[maxm];

 int n,m,d;

 bool vis[maxn];

 std::queue<int> q;

 int f[maxn][],g[];

 int edgeTot,head[maxn],nxt[maxm];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void spfa(int st)

 {

     for (int i=; i<=n; i++)

         if (f[i][st]!=INF) q.push(i);

     while (q.size())

     {

         int tt = q.front();

         q.pop(), vis[tt] = ;

         for (int i=head[tt]; i!=-; i=nxt[i])

         {

             int v = edges[i].y, w = edges[i].val;

             if (f[v][st] > f[tt][st]+w){

                 f[v][st] = f[tt][st]+w;

                 if (!vis[v]) vis[v] = , q.push(v);

             }

         }

     }

 }

 bool check(int num)

 {

     for (int i=; i<d; i++)

         if (((num>>i)&)&&((num>>(d+i))&)==) return ;

     return ;

 }

 void addedge(int u, int v)

 {

     int c = read();

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = Edge(u, c), nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 int main()

 {

     memset(head, -, sizeof head);

     memset(f, 0x3f3f3f3f, sizeof f);

     memset(g, 0x3f3f3f3f, sizeof g);

     n = read(), m = read(), d = read();

     for (int i=; i<=m; i++) addedge(read(), read());

     for (int i=; i<=d; i++)

         f[i][<<(i-)] = , f[n-i+][<<(d+i-)] = ;

     for (int i=; i<<<(d<<); i++)

     {

         for (int j=; j<=n; j++)

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

                 f[j][i] = std::min(f[j][i], f[j][s]+f[j][i-s]);

         spfa(i);

         for (int j=; j<=n; j++) g[i] = std::min(g[i], f[j][i]);

     }

     for (int i=; i<<<(d<<); i++)

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

             if (check(s)&&check(i-s))

                 g[i] = std::min(g[i], g[s]+g[i-s]);

     if (g[(<<(d<<))-] != INF)

         printf("%d\n",g[(<<(d<<))-]);

     else puts("-1");

     return ;

 }

END

秒客网

初涉斯坦纳树&&bzoj4774: 修路