P4784 [BalticOI2016]城市

2018-09-05 19:59:11


题意:给定一个无向图,求把重要节点联通的最小代价(重要节点<=5)


将指定点集合中的所有点连通,且边权总和最小的生成树称为最小斯坦纳树(Minimal Steiner Tree)

其实最小生成树是最小斯坦纳树的一种特殊情况,联通了图上所有节点

最小斯坦纳树可以用dp求解

令 $f[i][j]$ 表示以 $i$ 为根,指定集合中点的联通状态为 $j$ 的最小总权值

转移分为两重

  • 第一重:枚举当前状态的子集进行转移

    方程为: $f[i][j]=min(f[i][j],f[i][k]+f[i][j xor k])$

    枚举子集的技巧是: $for (k=j\&(j-1);k;k=j\&(k-1))$

  • 第二重:在当前状态下对其进行松弛操作

    方程为: $f[i][j]=min(f[i][j],f[k][j]+cost)$

    在这一重只需对这一种状态进行松弛即可,因为其他状态会通过第一重转移更新

    松弛操作可以通过spfa实现(如果spfa又双叒叕被卡了请使用堆优化dijkstra)

相关题目:[JLOI2015]管道连接 [WC2008]游览计划

现在时限扩大了,加上点常数优化就可以AC了orzzzzz

~虽然我不会写fread~

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node
{
    int to,nxt,dis;
}edge[N<<2];
struct P
{
    int x; ll d;
    inline friend bool operator < (P a,P b) {return a.d>b.d;}
};
int n,m,p,num,head[N];
ll f[N][32],inf,ans=1e18;
bool vis[N];
priority_queue<P>q;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int dis)
{
    edge[++num]=(node){to,head[from],dis};
    head[from]=num;
}
inline void dijkstra(int S)
{
    memset(vis,0,sizeof(vis));
    while (!q.empty())
    {
        int u=q.top().x; q.pop();
        if (vis[u]) continue; vis[u]=1;
        for (reg int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to,d=edge[i].dis;
            if (f[v][S]>f[u][S]+d)
            {
                f[v][S]=f[u][S]+d;
                q.push((P){v,f[v][S]});
            }
        }
    }
}
int main()
{
    n=read(),p=read(),m=read();
    memset(f,127/3,sizeof(f)); inf=f[0][0];
    for (reg int i=1;i<=p;i++) f[read()][1<<(i-1)]=0;
    for (reg int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add_edge(x,y,z); add_edge(y,x,z);
    }
    for (reg int i=1;i<(1<<p);i++)
    {
        for (reg int k=1;k<=n;k++)
        {
            for (reg int j=i&(i-1);j;j=i&(j-1))
              f[k][i]=min(f[k][i],f[k][j]+f[k][i^j]);
            if (f[k][i]<inf) q.push((P){k,f[k][i]});
        }
        dijkstra(i);
    }
    for (reg int i=1;i<=n;i++) ans=min(ans,f[i][(1<<p)-1]);
    printf("%lld\n",ans);
    return 0;
}