bzoj 4006: [JLOI2015]管道连接

题意：

题解：

差不多是斯坦纳树模板题吧。
$h_{i, S}$表示根在$i$，连通重要站集合$S$的最小代价。$f_S$表示连通频道集合$S$的最小代价。

代码：

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

const int inf = 0x3f3f3f3f;
int n, m, p, num = 0, fst[1010], f[1030], pt[11], mp[1010], re[1030], h[1010][1030];
struct edge
{
    int x, y, c, n;
} e[6010];
bool v[1010];

void ins(int x, int y, int c)
{
    e[++num] = {x, y, c, fst[x]};
    fst[x] = num;
}
void spfa(int S)
{
    static queue<int> q;
    memset(v, 0, sizeof(v));
    for (int i = 1; i <= n; i++)
        if (h[i][S] < inf)
        {
            q.push(i);
            v[i] = 1;
        }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for (int i = fst[x]; i; i = e[i].n)
        {
            int y = e[i].y;
            if (h[y][S] > h[x][S] + e[i].c)
            {
                h[y][S] = h[x][S] + e[i].c;
                if (!v[y])
                {
                    v[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        ins(x, y, c);
        ins(y, x, c);
    }
    for (int i = 0; i < p; i++)
    {
        int x, id;
        scanf("%d%d", &x, &id);
        x--;
        mp[id] = 1 << i;
        pt[x] |= mp[id];
        re[mp[id]] = id;
    }
    memset(h, 63, sizeof(h));
    memset(f, 63, sizeof(f));
    for (int i = 0; i < p; i++)
        h[re[1 << i]][1 << i] = 0;
    for (int S = 1; S < (1 << p); S++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int s = S & (S - 1); s; s = (s - 1) & S)
                h[i][S] = min(h[i][S], h[i][s] + h[i][s ^ S]);
        }
        spfa(S);
        int oo = inf;
        for (int i = 1; i <= n; i++)
            oo = min(oo, h[i][S]);
        for (int S2 = 1; S2 < (1 << p); S2++)
        {
            int hh = 0;
            for (int i = 0; i < p; i++)
                if (S2 & (1 << i))
                    hh |= pt[i];
            if ((hh & S) == hh)
                f[S2] = min(f[S2], oo);
        }/*
        printf("S: %d\n", S);
        for (int i = 1; i <= n; i++)
            printf("%d ", h[i][S]);
        puts("");*/
    }
    for (int S = 1; S < (1 << p); S++)
    {
        for (int s = S & (S - 1); s; s = S & (s - 1))
        {
            f[S] = min(f[S], f[s] + f[S ^ s]);
        }
    }/*
    for (int S = 1; S < (1 << p); S++)
        printf("%d ", f[S]);
    puts("");*/
    printf("%d\n", f[(1 << p) - 1]);
}