本文主要是介绍ZOJ 3613 Wormhole Transport（DP 斯坦纳树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个星球，其中有些星球上有多个工作，有些星球上有些资源（但是一个星球上的资源只能提供给一个工厂），知道在一些星球边建立边的代价，问使得得到资源的工厂的数目最多的多少，在些前提下代价最小是多少。
还是斯坦纳树，不懂看：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=205;
struct Edge
{int v,w;Edge *nxt;
}memo[N*N],*cur,*adj[N];int n,m,mask;
int d[N][1<<10],dp[1<<10];
bool vis[N][1<<10];
int fac[N],rec[N],st[N];
queue<int> que;void addEdge(int u,int v,int w)
{cur->v=v; cur->w=w;cur->nxt=adj[u];adj[u]=cur++;
}
void up(int &a,int b){ a=min(a,b); }
bool judge(int s)
{int cnt=0;for(int i=1;i<=n;i++){if(s&st[i]) cnt+=fac[i],cnt-=rec[i];}return cnt>=0;
}
int getnum(int s)
{int cnt=0;for(int i=1;i<=n;i++){if(s&st[i]) cnt+=rec[i];}return cnt;
}
void spfa()
{while(que.size()){int u=que.front()/1000,s=que.front()%1000;que.pop(); 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*1000+s),vis[v][s]=1;}}}
}
void init()
{cur=memo;memset(adj,0,sizeof(adj));memset(vis,0,sizeof(vis));memset(dp,63,sizeof(dp));memset(d,63,sizeof(d));memset(st,0,sizeof(st));
}
int main()
{while(scanf("%d",&n)!=EOF){init();int ans=0,fac_cnt=0,rec_cnt=0;for(int i=1;i<=n;i++){scanf("%d%d",&fac[i],&rec[i]);if(fac[i]&&rec[i]) fac[i]--,rec[i]--,ans++;if(fac[i]) {st[i]=(1<<(fac_cnt++));d[i][st[i]]=0;}if(rec[i]){st[i]=(1<<(4+rec_cnt++));d[i][st[i]]=0;}}scanf("%d",&m);while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);addEdge(v,u,w);}mask=(1<<(4+rec_cnt))-1;for(int s=1;s<=mask;s++){for(int i=1;i<=n;i++){if(st[i]&&!(st[i]&s)) continue;for(int p=(s-1)&s;p;p=(p-1)&s){int s1=p|st[i],s2=(s-p)|st[i];up(d[i][s],d[i][s1]+d[i][s2]);}if(d[i][s]<1e9&&!vis[i][s])que.push(i*1000+s),vis[i][s]=1;}spfa();}for(int s=1;s<=mask;s++)for(int i=1;i<=n;i++)dp[s]=min(dp[s],d[i][s]);int cnt=0,cost=0;for(int s=1;s<=mask;s++){if(judge(s)&&dp[s]<1e9){for(int p=(s-1)&s;p;p=(p-1)&s){if(judge(p)&&judge(s-p)&&dp[p]<1e9&&dp[s-p]<1e9)up(dp[s],dp[p]+dp[s-p]);}int tmp=getnum(s);if(cnt<tmp||(cnt==tmp&&cost>dp[s]))cnt=tmp,cost=dp[s];}}printf("%d %d\n",cnt+ans,cost);}return 0;
}
这篇关于ZOJ 3613 Wormhole Transport（DP 斯坦纳树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
