斯坦纳树

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

上述文字来自百度百科，更\(OI\)化的表达参见这道模板题

现在我们来考虑解决这个问题。

看到\(K\)很小，考虑状压\(dp\)，有一个显然的结论是：答案的图一定不存在环，即答案是一棵树。

设\(f_{i,S}\)为以\(i\)为根，目前已选点集为\(S\)的最小代价。

考虑划分子树转移

考虑\(i\)仅有一条出边时，需要枚举\(i\)的邻边转移

第一种转移枚举子集转移即可，第二种转移对于每种点集\(S\)跑一遍\(Dijkstra\)即可，注意枚举\(S\)时升序枚举。

时间复杂度\(O(n\times 3^k+m\ \rm{log}\ m\times 2^k)\)

Code

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

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    return x * f;
}

const int N = 105;
const int M = 1005;
const int K = 11;

struct node{ int to, nxt, val; }edge[M];
int head[N], tot, x;
int f[N][1 << K];
bool vis[N];

void addedge(int u, int v, int w)
{
    edge[++tot] = (node){ v, head[u], w };
    head[u] = tot;
}

priority_queue<pair<int, int> > Q;

void Dijkstra(int s)
{
    memset(vis, 0, sizeof(vis));
    while (!Q.empty())
    {
        int u = Q.top().second;
        Q.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        for (int i = head[u]; i; i = edge[i].nxt)
        {
            int v = edge[i].to, w = edge[i].val;
            if (f[v][s] > f[u][s] + w)
            {
                f[v][s] = f[u][s] + w;
                Q.push({-f[v][s], v});
            }
        }
    }
}

int main()
{
    int n = read(), m = read(), k = read();
    for (int i = 1; i <= m; ++i) 
    {
        int u = read(), v = read(), w = read();

        addedge(u, v, w);
        addedge(v, u, w);
    }

    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= k; ++i) 
    {
        x = read();
        f[x][1 << (i - 1)] = 0;
    }

    for (int s = 1; s < (1 << k); ++s)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int s1 = s & (s - 1); s1; s1 = s & (s1 - 1))
            {
                int s2 = s1 ^ s;
                f[i][s] = min(f[i][s], f[i][s1] + f[i][s2]);
            }
            Q.push({-f[i][s], i});
        }
        Dijkstra(s);
    }
    printf("%d\n", f[x][(1 << k) - 1]);
    return 0;
}

例题 JLOI2015 管道连接

这题与上题的区别仅是关键点分为了\(K\)类。

先和上题一样求出\(f_{i,S}\)

设\(g_S\)为已选点集为\(S\)的最小代价。

初值\(g_S=min\{f_{i,S}\}\)，\(S\)的点来自同一关键点类。

子集转移即可。

Code

习题

WC2008 游览计划