斯坦纳树相关

1.复杂度 O(n*3^k+cE*2^k)

c为SPFA复杂度中的常数,E为边的数量,但几乎达不到全部边的数量,甚至非常小。3^k来自于子集的转移sum{C(i,n)*2^i} (1<=i<=n),用二项式展开求一下和。

2.如果最后可以是森林,最后还要dp一次,f[state]表示状态为state时的最小花费,首先

for(j=0;j<(1<<cc+1);j++)
    for(i=1;i<=n;i++)
        f[j]=min(f[j],dp[i][j]);

表示最后是一棵树的情况。然后
 

for(j=1;j<(1<<cc+1);j++)
{
    for(sub=(j-1)&j;sub;sub=(sub-1)&j)
    {
        if(!check(sub) || !check(j-sub) || f[sub]>=inf || f[j-sub]>=inf) continue;
        f[j]=min(f[j],f[sub]+f[j-sub]);
    }
}

表示有一些独立的斯坦纳树组合,这些子集枚举时往往对state有约束条件,需要check。最后的答案state往往也有约束条件。

 
hdoj3311 Dig The Wells
加一个点0,向各个点连边,权为各个点挖井的费用,求包含n个和尚和0点的最小斯坦纳树。这样就解决了边权的问题

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 2010
#define K 8
#define maxe 20000+10
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge{
    int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m,p;
int dp[maxn][1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void init()
{
    int i,j;
    memset(dp,inf,sizeof(dp));
    memset(st,0,sizeof(st));
    memset(in,0,sizeof(in));
    for(i=0;i<=n;i++) st[i]=(1<<i);
    for(i=0;i<=n+m;i++)
        dp[i][st[i]]=0;
    return;
}
bool update(int &a,int b)
{
    if(b<a) {a=b;return 1;}
    return 0;
}
void spfa(int state)
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u][state]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            int state2=state|st[v];
            if(dp[u][state]+w<dp[v][state2])
            {
                dp[v][state2]=dp[u][state]+w;
                if(state2!=state || in[v][state]) continue;
                in[v][state]=1;q.push(v);
            }
        }
    }
    return;
}
void SteinerTree()
{
    int i,j,sub;
    for(j=1;j<(1<<n+1);j++)
    {
        for(i=0;i<=n+m;i++)
        {
            bool flag=1;
            if(st[i] && (st[i]&j)==0) continue;
            for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            {
                int x=sub|st[i],y=(j-sub)|st[i];
                if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
                flag=update(dp[i][j],dp[i][x]+dp[i][y]);
            }
            //if(!flag) continue;
            if(dp[i][j]<inf)
            q.push(i),in[i][j]=1;
        }
        spfa(j);
    }
}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n+m;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            add(0,i,tmp);add(i,0,tmp);
        }
        for(i=1;i<=p;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        init();
        SteinerTree();
        int ans=inf;
        for(i=0;i<=n+m;i++)
            if(dp[i][(1<<n+1)-1]<ans) ans=dp[i][(1<<n+1)-1];
        printf("%d\n",ans);
    }
    return 0;
}

hdoj4085 Peach Blossom Spring
最后可能是森林,还要dp一次

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 60
#define K 13
#define maxe 3000+10
#define inf 0x3f3f3f3f//注意wa很可能是inf不够大。。
using namespace std;
typedef struct Edge{
    int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m,k;
int dp[maxn][1<<K],f[1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void init()
{
    int i;
    memset(dp,inf,sizeof(dp));
    memset(f,inf,sizeof(f));
    memset(st,0,sizeof(st));
    memset(in,0,sizeof(in));
    for(i=1;i<=k;i++) st[i]=(1<<i-1);
    for(i=n-k+1;i<=n;i++) st[i]=(1<<i-n+k+k-1);
    for(int i=1;i<=n;i++)
        dp[i][st[i]]=0;
    return;
}
void spfa(int state)
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u][state]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            int state2=state|st[v];
            if(dp[u][state]+w<dp[v][state2])
            {
                dp[v][state2]=dp[u][state]+w;
                if(state2!=state || in[v][state]) continue;
                in[v][state]=1;q.push(v);
            }
        }
    }
    return;
}
bool check(int state)
{
    int i,j;
    int cnt=0;
    for(i=0;i<k;i++)
    {
        if(state&(1<<i)) cnt++;
        if(state&(1<<i+k)) cnt--;
    }
    return cnt==0;
}
int SteinerTree()
{
    int i,j,sub;
    for(j=1;j<(1<<(2*k));j++)
    {
        for(i=1;i<=n;i++)
        {
            if(st[i] && (st[i]&j)==0) continue;
            for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            {
                int x=sub|st[i],y=(j-sub)|st[i];

                if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
                dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][y]);
            }
            if(dp[i][j]>=inf) continue;
            q.push(i);in[i][j]=1;
        }
        spfa(j);
    }
    for(j=0;j<(1<<2*k);j++)
        for(i=1;i<=n;i++)
            f[j]=min(f[j],dp[i][j]);
    for(j=1;j<(1<<2*k);j++)
    {
        for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            if(check(sub) && check(j-sub))
                f[j]=min(f[j],f[sub]+f[j-sub]);
    }
    return f[(1<<2*k)-1];
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        init();
        int ans=SteinerTree();
        if(ans>=inf) printf("No solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

zoj3613 Wormhole Transport
同样最后可能是森林,要dp一次
注意check函数,合法条件是资源数>=工厂数,最后的最大工厂数取决于集合中资源数

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 210
#define K 10
#define maxe 20000+10
#define inf (0x3f3f3f3f)*2//注意wa很可能是inf不够大。。
using namespace std;
typedef struct Edge{
    int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m;
int dp[maxn][1<<K],f[1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
int p[maxn],s[maxn];
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
int bit[10],cc;
void init()
{
    int i;
    memset(dp,inf,sizeof(dp));
    memset(f,inf,sizeof(f));
    memset(st,0,sizeof(st));
    memset(in,0,sizeof(in));
    //记得对关键点的st[]赋权
    cc=-1;
    for(i=1;i<=n;i++)
    {
        if(p[i] || s[i]){ cc++;st[i]=(1<<cc);bit[cc]=i;}
    }
    for(i=1;i<=n;i++)
        dp[i][st[i]]=0;
    return;
}
void spfa(int state)
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u][state]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            int state2=state|st[v];
            if(dp[u][state]+w<dp[v][state2])
            {
                dp[v][state2]=dp[u][state]+w;
                if(state2!=state || in[v][state]) continue;
                in[v][state]=1;q.push(v);
            }
        }
    }
    return;
}
bool check(int state)
{
    int i,tmp1=0,tmp2=0;
    for(i=0;i<=cc;i++)
    {
        if(state&(1<<i))
            tmp1+=p[bit[i]],tmp2+=s[bit[i]];
    }
    return tmp1>=tmp2;
}
void SteinerTree()
{
    int i,j,sub;
    for(j=1;j<(1<<cc+1);j++)
    {
        for(i=1;i<=n;i++)
        {
            if(st[i] && (st[i]&j)==0) continue;
            for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            {
                int x=sub|st[i],y=(j-sub)|st[i];
                if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
                dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][y]);
            }
            if(dp[i][j]>=inf) continue;
            q.push(i);in[i][j]=1;
        }
        spfa(j);
    }
    for(j=0;j<(1<<cc+1);j++)
        for(i=1;i<=n;i++)
            f[j]=min(f[j],dp[i][j]);
    for(j=1;j<(1<<cc+1);j++)
    {
        for(sub=(j-1)&j;sub;sub=(sub-1)&j)
        {
            if(!check(sub) || !check(j-sub) || f[sub]>=inf || f[j-sub]>=inf) continue;
            f[j]=min(f[j],f[sub]+f[j-sub]);
        }
    }
}
int cal(int state)
{
    int i,j,ans=0;
    for(i=0;i<=cc;i++)
    {
        if(state&(1<<i))
            ans+=s[bit[i]];
    }
    return ans;
}
int main()
{
    int i,j;
    int u,v,w;
    while(~scanf("%d",&n))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(p,0,sizeof(p));memset(s,0,sizeof(s));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i],&s[i]);
        }
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        init();
        SteinerTree();
        int ans=0,cost=0;
        for(j=0;j<(1<<cc+1);j++)
        {
            if(!check(j) || f[j]>=inf) continue;
            int tmp=cal(j);
            if(tmp>ans)
            {
                ans=tmp;
                cost=f[j];
            }
            else if(tmp==ans && f[j]<cost) cost=f[j];
        }
        printf("%d %d\n",ans,cost);





    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>