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;
}
