题解P3264 [JLOI2015]管道连接

· · 题解

最小斯坦纳树应用

最小斯坦纳树是一种状压 dp ，用来求在一个无向连通图里有几个关键点，边有权值，选择边的子集，使关键点连通且权值和最小的问题。

首先这个子集必然为一棵树，否则去掉一条边可定不会变劣。

令 f_{i,j} 表示在以 i 为根的树里，已经有状态 j 的点连通的最小代价。

两种转移：

换根：f_{i,j}= \min(f_{i,j},f_{k,j}+w(i,k))

子集合并：f_{i,j}=\min(f_{i,j},f_{i,s}+f_{i,j \land s})

第一种我们可以用最短路的方法，用 dij 堆优化做。

第二种可以枚举子集，暴力维护。

时间复杂度 ：O(n3^k+m \log m 2^n)

在求完最小斯坦纳树后，继续枚举子集，一个子集无限制，一个子集为自己子集中包含的频道的所有情报站。

以此做一个 dp 即可。

代码如下

// Problem: P3264 [JLOI2015]管道连接
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3264
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 2022-01-21 14:27:26
// Author : louhao088
// 

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lowbit (x&-x)
#define int long long
const int maxn=1024+5,M=34005;
inline int read()
{
    char ch=getchar();bool f=0;int x=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1)x=-x;return x;
}
inline void print(int x)
{
    static int a[55];int top=0;
    if(x<0) putchar('-'),x=-x;
    do{a[top++]=x%10,x/=10;}while(x);
    while(top) putchar(a[--top]+48);
}
int n,m,f[maxn][maxn],num[15],k,x,y,z,vis[maxn],w[maxn],g[maxn],id[maxn],a[maxn];
vector<pi>e[maxn];
priority_queue<pi>q;
void dij(int s)
{
    memset(vis,0,sizeof vis);
    while(!q.empty())
    {
        int x=q.top().se;q.pop();
        if(vis[x])continue;vis[x]=1;
        for(auto i:e[x])
            if(f[i.fi][s]>f[x][s]+i.se)
                f[i.fi][s]=f[x][s]+i.se,q.push(mp(-f[i.fi][s],i.fi));
    }
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read(),k=read();memset(f,0x3f,sizeof f);
    for(int i=1;i<=m;i++)
        x=read(),y=read(),z=read(),e[x].pb(mp(y,z)),e[y].pb(mp(x,z));
    for(int i=1;i<=n;i++)f[i][0]=0;
    for(int i=1;i<=k;i++)
        id[i]=read(),a[i]=read(),num[id[i]]+=(1<<(i-1)),f[a[i]][(1<<(i-1))]=0;
    for(int j=1;j<(1<<k);j++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int s=j&(j-1);s;s=j&(s-1))
                f[i][j]=min(f[i][s]+f[i][s^j],f[i][j]);
            if(f[i][j]!=0x3f3f3f3f)q.push(mp(-f[i][j],i));
        }
        dij(j);
    }
    memset(w,0x3f,sizeof w),memset(g,0x3f,sizeof g);
    for(int j=0;j<(1<<k);j++)
        for(int i=1;i<=n;i++)w[j]=min(w[j],f[i][j]);
    g[0]=0;
    for(int j=1;j<(1<<k);j++)
    {
        for(int s=j;s;s=j&(s-1))
        {
            int res=0;
            for(int i=0;i<k;i++)if(s&(1<<i))res=res|num[id[i-1]];
            g[j]=min(g[j],g[s^j]+w[res]);
        }
    }
    cout<<g[(1<<k)-1]<<endl;
    return 0;
}