标签：leq int 边权最小笔记斯坦纳为根

最小斯坦纳树

定义

摘自百度百科的定义：

斯坦纳树问题是组合优化问题，与 最小生成树相似 ，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。

实现

例题：P6192 【模板】最小斯坦纳树 - 洛谷

题目描述

给定一个包含 \(n\) 个结点和 \(m\) 条带权边的无向连通图 \(G=(V,E)\)。

再给定包含 \(k\) 个结点的点集 \(S\)，选出 \(G\) 的子图 \(G'=(V',E')\)，使得：

\(S\subseteq V'\)；
\(G'\) 为连通图；
\(E'\) 中所有边的权值和最小。

你只需要求出 \(E'\) 中所有边的权值和。

数据范围

对于 \(100\%\) 的数据，\(1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6\)。

保证给出的无向图连通，但可能存在重边和自环。

分析

要解决最小斯坦纳树，我们需要使用最短路算法 + 状压 DP。

首先，很显然的一点是：\(G'\) 是一棵树。

证明：若 \(G′\) 中包含环，那么将环中边权最大的边删去后，\(G′\) 仍连通且边权和变得更小，与前面假设的边权和最小矛盾，故 \(G′\) 不含环。

然后，我们发现 \(k\) 很小，可以往状压方面去想。设 \(f[i][S]\) 表示以 \(i\) 为根的树，选择的点集为 \(S\)（题目里面说的 \(k\) 个点）时的最小边权和，则可得到方程：

\[\begin{aligned} f[i][S] &= f[i][S - T] + f[i][T]\:\:(T \subseteq S)\\ f[i][S] &= f[j][S] + w(i, j) \end{aligned} \]

第一个式子可将 \(S\) 的两个互为补集的子集的状态合并。
第二个式子可将 \(i\) 的状态转移到另一个相邻节点。注意这个式子，像不像最短路？都是三角不等式，我们只需在状压时对每个状态跑一次最短路即可。

考虑 DP 的顺序：不难想到按 \(S\) 从小到大枚举即可。

考虑答案的产生：\(\forall i \in S\)，\(f[i][S]\) 均为答案。

证明：因为 \(f[i][S]\) 表示以 \(i\) 为根结点且包含 \(S\) 的树的最小边权和，而最小斯坦纳树显然包括 \(S\)，所以 \(S\) 中的任意一点为根都可以作为答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 105, maxm = 505, maxk = 10;
int n, m, k;
int head[maxn];
struct Edge {
    int to, weight, next;
} edge[maxm << 1];
struct Node {
    int id, dis;
    bool operator < (const Node &rhs) const {
        return dis > rhs.dis;
    }
};
int f[maxn][1 << maxk];

inline void insertEdge(int u, int v, int w) {
    static int edgecnt;
    edge[++edgecnt].to = v;
    edge[edgecnt].weight = w;
    edge[edgecnt].next = head[u];
    head[u] = edgecnt;
}

inline void dijkstra(int S) {
    priority_queue<Node> que;
    for (int i = 1; i <= n; i++) {
        if (f[i][S] == 0x3f3f3f3f) continue;
        que.push(Node{ i, f[i][S] }); // 只有已经松弛过的点才加入优先队列
    }
    while (!que.empty()) {
        int u = que.top().id;
        que.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].weight;
            if (f[v][S] > f[u][S] + w) {
                f[v][S] = f[u][S] + w; // 和最短路是一样的
                que.push(Node{ v, f[v][S] });
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        insertEdge(u, v, w);
        insertEdge(v, u, w);
    }
    memset(f, 0x3f, sizeof(f)); // 记得初始化为正无穷
    int vertex;
    for (int i = 1; i <= k; i++) {
        scanf("%d", &vertex);
        f[vertex][1 << (i - 1)] = 0; // 当集合中只包含一个点的时候，边权和显然为 0
    }
    for (int i = 1; i <= n; i++) {
        f[i][0] = 0; // 一个点都没有显然也是 0
    }
    for (int S = 1; S < (1 << k); S++) {
        for (int i = 1; i <= n; i++) { // 以每个点为根都跑一遍
            for (int j = S & (S - 1); j; j = S & (j - 1)) { // 枚举当前 S 的子集（不含空集和 S 本身，原因自己想）
                f[i][S] = min(f[i][S], f[i][S ^ j] + f[i][j]);
            }
        }
        dijkstra(S); // 最短路
    }
    printf("%d", f[vertex][(1 << k) - 1]); // S 中的每个点都可作为答案，所以就干脆直接用最后读入的 vertex
    return 0;
}