BZOJ 5180 [Baltic2016]Cities

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=5180

题意：给定 n 个点，m 条双向边的图。其中有 k 个点是重要的。每条边都有一定的长度。现在要你选定一些边来构成一个图，要使得 k 个重要的点相互连通，求边的长度和的最小值。

斯坦纳树裸题... 第一次写... 就是个状压 dp 嘛...

\(f_{S,i}\) 表示以 i 为根的子树，联通状态为 S 的最小费用，不同层转移是一个枚举子集的过程，同层的转移用每条边去转移，发现具有后效性，所以用最短路跑。

交了两发卡了 100s 的 OJ...

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
#define M 200005
#define K 32
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,k,m;
struct zgz
{
    int next,to,val;
}edge[M<<1];
int head[N],cnt=1;
void add(int from,int to,int val)
{
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
ll f[K][N];
int vis[N],T;
inline ll Mn(ll a,ll b)
{return a<b?a:b;}
typedef pair<ll,int> pr;
priority_queue<pr,vector<pr>,greater<pr> > q;
int main()
{
    n=read(),k=read(),m=read();
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<k;i++)f[1<<i][read()]=0;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    for(int S=1;S<(1<<k);S++)
    {
        for(int i=S;i;i=S&(i-1))
        for(int j=1;j<=n;j++)f[S][j]=Mn(f[S][j],f[i][j]+f[S^i][j]);
        for(int i=1;i<=n;i++)q.push(make_pair(f[S][i],i));
        T++;
        while(!q.empty())
        {
            int x=q.top().second;q.pop();
            if(vis[x]==T)continue ;
            vis[x]=T;
            for(int i=head[x];i;i=edge[i].next)
            {
                int to=edge[i].to,val=edge[i].val;
                if(f[S][to]>f[S][x]+val)
                {
                    f[S][to]=f[S][x]+val;
                    q.push(make_pair(f[S][to],to));
                }
            }
        }
    }
    ll ans=f[0][0];
    for(int i=1;i<=n;i++)
    ans=Mn(ans,f[(1<<k)-1][i]);
    printf("%lld\n",ans);
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 100005

#define M 200005

#define K 32

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,k,m;

struct zgz

{

int next,to,val;

}edge[M<<1];

int head[N],cnt=1;

void add(int from,int to,int val)

{

edge[cnt].to=to;

edge[cnt].val=val;

edge[cnt].next=head[from];

head[from]=cnt++;

}

ll f[K][N];

int vis[N],T;

inline ll Mn(ll a,ll b)

{return a<b?a:b;}

typedef pair<ll,int> pr;

priority_queue<pr,vector<pr>,greater<pr> > q;

int main()

{

n=read(),k=read(),m=read();

memset(f,0x3f,sizeof(f));

for(int i=0;i<k;i++)f[1<<i][read()]=0;

for(int i=1;i<=m;i++)

{

int x=read(),y=read(),z=read();

add(x,y,z),add(y,x,z);

}

for(int S=1;S<(1<<k);S++)

{

for(int i=S;i;i=S&(i-1))

for(int j=1;j<=n;j++)f[S][j]=Mn(f[S][j],f[i][j]+f[S^i][j]);

for(int i=1;i<=n;i++)q.push(make_pair(f[S][i],i));

T++;

while(!q.empty())

{

int x=q.top().second;q.pop();

if(vis[x]==T)continue ;

vis[x]=T;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(f[S][to]>f[S][x]+val)

{

f[S][to]=f[S][x]+val;

q.push(make_pair(f[S][to],to));

}

ll ans=f[0][0];

for(int i=1;i<=n;i++)

ans=Mn(ans,f[(1<<k)-1][i]);

printf("%lld\n",ans);

}

zgz233

zgz233

BZOJ 5180 [Baltic2016]Cities

l1ll5

Comments | NOTHING