本文主要是介绍HDU 4085 Peach Blossom Spring（DP，斯坦纳树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你n,m,k ，分别表示有n个点，m条边，每条边有一个权值，表示修复这条边需要的代价，从前k个点中任取一个使其和后k个点中的某一个点，通过边连接，并且必须是一一对应，问最小的代价是多少。同样是斯坦纳树，不过最后得到的答案可能是森林，所以最后要跑一个DP。如果不懂斯坦纳树，看：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define INF 2000000
const int N=60;
struct Edge
{int v,w;Edge *nxt;
}memo[N*N],*cur,*adj[N];int n,m,K,mask;
int st[N],vis[N][1<<11];
int d[N][1<<11],dp[1<<11];
queue<int>que;void addEdge(int u,int v,int w)
{cur->v=v; cur->w=w;cur->nxt=adj[u]; adj[u]=cur++;
}
bool check(int s)
{int res=0;for(int i=0;s;i++,s>>=1)res+=(s&1)*(i<K?1:-1);return (res==0?true:false);
}
void spfa()
{while(que.size()){int top=que.front(); que.pop();int u=top/10000,s=top%10000;vis[u][s]=0;for(Edge* it=adj[u];it;it=it->nxt){int v=it->v,w=it->w;if(d[v][s|st[v]]>d[u][s]+w){d[v][s|st[v]]=d[u][s]+w;if((s|st[v])==s&&!vis[v][s]) que.push(v*10000+s),vis[v][s]=1;}}}
}
void init()
{cur=memo; mask=(1<<(2*K))-1;memset(st,0,sizeof(st));memset(vis,0,sizeof(vis));memset(adj,0,sizeof(adj));for(int i=1;i<=n;i++)for(int j=0;j<=mask;j++) d[i][j]=INF;
}
int main()
{int t;scanf("%d",&t);while(t--){int u,v,w;scanf("%d%d%d",&n,&m,&K);init();for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);addEdge(v,u,w);}for(int i=1;i<=K;i++){st[i]=1<<(i-1); d[i][st[i]]=0;st[n-i+1]=(1<<(K+(i-1))); d[n-i+1][st[n-i+1]]=0;}for(int s=0;s<=mask;s++){for(int i=1;i<=n;i++){for(int p=(s-1)&s;p;p=(p-1)&s)d[i][s]=min(d[i][s],d[i][p|st[i]]+d[i][(s-p)|st[i]]);if(d[i][s]<INF&&!vis[i][s]) que.push(i*10000+s),vis[i][s]=1;}spfa();}for(int s=0;s<=mask;s++){dp[s]=INF;for(int i=1;i<=n;i++) dp[s]=min(dp[s],d[i][s]);}for(int s=1;s<=mask;s++)if(check(s))for(int p=(s-1)&s;p;p=(p-1)&s)if(check(p)) dp[s]=min(dp[s],dp[p]+dp[s-p]);if(dp[mask]>=INF) puts("No solution");else printf("%d\n",dp[mask]);}return 0;
}
这篇关于HDU 4085 Peach Blossom Spring（DP，斯坦纳树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
