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