斯坦纳树有什么用

个人一点粗浅理解……

最基本形式的斯坦纳树问题（以下简称母问题）：给定图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
     
       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
      
        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
       
        >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\n",g[(1<<(d<<1))-1]);82     else puts("-1");83     return 0;84 }

END

转载于:https://www.cnblogs.com/antiquality/p/9708971.html

你可能感兴趣的文章