洛谷P3264 [JLOI2015]管道连接题解

题目链接：P3264 [JLOI2015]管道连接

题意：

cxy 最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。

该部门有 \(n\) 个情报站，用 \(1\) 到 \(n\) 的整数编号。给出 \(m\) 对情报站 \((u_i,v_i)\) 和费用 \(w_i\)，表示情报站 \(u_i\) 和 \(v_i\) 之间可以花费 \(w_i\) 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 \(u_i\) 和 \(v_i\) 建立了通道，那么它们建立了通道连接；若 \(u_i\) 和 \(v_i\) 均与 \(t_i\) 建立了通道连接，那么 \(u_i\) 和 \(v_i\) 也建立了通道连接。

现在在所有的情报站中，有 \(p\) 个重要情报站，其中每个情报站有一个特定的频道。 cxy 面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。

输入格式：

第一行包含三个整数 \(n,m,p\)，表示情报站的数量，可以建立的通道数量和重要情报站的数量。

接下来 \(m\) 行，每行包含三个整数 \(u_i,v_i,w_i\)，表示可以建立的通道。

最后有 \(p\) 行，每行包含两个整数 \(c_i,d_i\)，表示重要情报站的频道和情报站的编号。

输出格式：

输出一行一个整数，表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。

数据范围：

对于 \(100\%\) 的数据，\(1\le c_i\le p\le10\)，\(1\le u_i,v_i,d_i \le n \le 1000\)，\(0\le m \le 3000\)，\(0\le w_i \le2\times 10^4\)。

\(\mathcal{Part\ 1}\)

建议配合斯坦纳树学习笔记食用

可以发现这不是朴素地求最小斯坦纳树，而是求最小斯坦纳森林。

形式化地，给定无向图 \(G=(V,E)\) 和 \(c\) 个不相交的关键集合 \(P_1,P_2,\cdots,P_c~(P_i \subseteq V)\)

设最小斯坦纳森林为原图的一个子图 \(G^{\prime} = (V^{\prime},E^{\prime})\)

则 \(\forall u,v\in P_i\) 满足 \(u,v\) 连通（不需要保证关键集合间连通）

并且 \(\sum_{(u,v)\in E^{\prime}}w(u,v)\) 取到最小值，显然 \(V^{\prime} \supseteq \left(\bigcup_{1\le i \le c} P_i\right)\)。

\(\mathcal{Part\ 2}\)

题目给出了 \(k\) 个关键点 \(p_i(1\le i \le k)\)，每个关键点有一个颜色 \(c_i\) ，仅要求 \(c_i\) 相同的关键点连通。

依旧考虑状压dp。设 \(f_{S,i}\) 表示包含关键子集 \(S\) 中所有点，且钦定 \(i\) 为树根时的最小代价。

然后我们直接把「所有的关键点（不考虑颜色）构成的集合」看作全集 \(U\) 跑一遍

这样我们就得到了 \(U\) 的所有子集的答案。不妨记 \(w_S = \min\{f_{S,i}\}\) ，\(d_S = \left\{p_i\mid c_i \in S\right\}\) 。

\(\mathcal{Part\ 3}\)

设 \(g_{S}\) 表示包含集合 \(S\) 中每种颜色（的全部结点），并且 \(S\) 中「同种颜色的点均连通」时的最小代价，则 \[ g_S \le \min_{1\le i \le n}\{f_{d_S,i}\} = w_{d_S} \] 这是一个上界，其意义为直接求其最小斯坦纳树。（因此我们在转移的时候枚举的不是真子集，而是子集）

接着我们可以用子集枚举来转移，因为我们并不知道哪些 \(P_i\) 最终会连通（当然也可能都不连通）

这里的转移有两种方法，第一种是令 \(g_S = +\infty\) ，然后用以下公式转移 \[ g_S \downarrow \min_{T \subseteq S}\left\{w_{d_T} + g_{S\setminus T}\right\} \] 注意这里枚举的是子集，因为 \(T=S\) 时就是刚刚说的上界，别忘了算进去（

还有一种转移方式是令 \(g_S = w_{d_S}\) ，然后用以下公式转移（ \(\subset\) 表示真包含） \[ g_S \downarrow \min_{T \subset S}\left\{g_T + g_{S\setminus T}\right\} \] 当然这两种转移本质上是一样的。

最后的答案就是 \(g_U\) ，\(U\) 表示所有颜色的集合。

\(\mathcal{Part\ 4}\)

等等，这样直接加不会算重边吗？事实上确实可能会。

但是我们会枚举到所有的情况，容易发现出现重边的情况一定不是最优的，因为可以去掉重边。

注意，这道题的题解区一大片都是假的，因为这道题不能用 spfa ，但是数据太水了一堆都过了。

自己造了几组 hack，但是卡不掉，可能是数据范围的问题吧。（甚至还有乱搞的复杂度，我真服了）

\(\mathcal{Part\ 5}\)

时间复杂度 \(\mathcal{O}(n3^k + m \log m 2^k)\) ，需要开O2。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e3+15))
#define M ((int)(3e3+15))
#define L ((1 << 10) + 5)

int n,m,k,pos=1,head[N];
int f[L][N],g[L],w[L],st[L],id[15],p[15],num[15];
struct Edge{ int v,w; };
vector<Edge> vec[N];
priority_queue<pii> q; bitset<N> vis;
void addEdge(int u,int v,int w) { vec[u].push_back({v,w}); }
void Dijkstra(int S)
{
    int *d = f[S]; vis = 0; while(!q.empty()) q.pop();
    for(int i=0; i<n; i++) if(d[i] != INF) q.push({-d[i],i});
    while(!q.empty())
    {
        int u = q.top().second; q.pop();
        if(vis[u]) continue; vis[u] = 1;
        for(int i=0,v,w; i<vec[u].size(); i++)
        {
            v = vec[u][i].v, w = vec[u][i].w;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({-d[v], v});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("spfa5.in","r",stdin);
    // freopen("spfa5.out","w",stdout);

    read(n); read(m); read(k);
    memset(f,0x3f,sizeof(f));
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u); read(v); read(w); --u; --v;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    for(int i=1,x,y; i<=k; i++)
    {
        read(id[i]); read(p[i]); --p[i];
        num[id[i]] |= (1 << (i-1)); f[1 << (i-1)][p[i]] = 0;
    }
    int mx = (1 << k) - 1;
    for(int S=1; S<=mx; S++)
    {
        for(int T = S&(S-1); T && (T >= (S^T)); T = (T-1) & S)
            for(int i=0; i<n; i++)
                down(f[S][i], f[T][i] + f[S ^ T][i]);
        Dijkstra(S); w[S] = INF; g[S] = INF;
        for(int i=0; i<n; i++) down(w[S], f[S][i]);
        for(int i=0; i<k; i++) if((S >> i) & 1) st[S] |= num[id[i]];
    }
    g[0] = 0;
    for(int S=1; S<=mx; S++)
        for(int T = S; T && (T >= (S^T)); T = (T-1) & S)
            down(g[S], g[S^T] + w[st[T]]);
    write(g[mx]);
    return 0;
}