首页 > 代码库 > BZOJ4349 最小树形图
BZOJ4349 最小树形图
Description
小C现在正要攻打科学馆腹地------计算机第三机房。而信息组的同学们已经建好了一座座堡垒，准备迎战。小C作为一种高度智慧的可怕生物，早已对同学们的信息了如指掌。
攻打每一个人的堡垒需要一个代价，而且必须攻打若干次才能把镇守之人灭得灰飞烟灭。
当小C在绞尽脑汁想攻打方案时，突然从XXX的堡垒中滚出来一个纸条：一个惊人的秘密被小C发现了：原来各个堡垒之间会相互提供援助，但是当一 个堡垒被攻打时，他对所援助的堡垒的援助就会停止，因为他自己已经自身难保了。也就是说，小C只要攻打某个堡垒一次之后，某些堡垒就只需要花更小的代价攻 击了。
现在，要你求消灭全机房要用掉代价最小多少。
Input
第一行一个数N，(N<=50),表示机房修建的堡垒数。
接下来N行，每行两个数，第一个实数Ai表示攻打i号堡垒需要的代价Ai(0<Ai<=1000)。第二个数Bi(0<Bi<100)表示i号堡垒需要被攻打Bi次。
接下来一个数k，表示总共有k组依赖关系。
接下来k行每行三个数x，y，z(x,y,为整数，z为实数)，表示攻打过一次x号堡垒之后，攻打y号堡垒就只要花z的代价，保证z比y原来的代价小。
不需要攻打的城堡不允许攻打。
Output
一行，一个实数表示消灭全机房要用的最小代价，保留两位小数。
Sample Input
3
10．00 1
1.80 1
2.50 2
2
1 3 2.00
3 2 1.50
10．00 1
1.80 1
2.50 2
2
1 3 2.00
3 2 1.50
Sample Output
15.50
正解：最小树形图（朱-刘算法）
解题报告：
然而我其实用搜索艹掉了这道题。
首先第一步剪枝，我们可以考虑对于所有商品预处理一下他能够到达的最便宜的状态是多少，如果当前已经能够取到最便宜了的话，就把所有已经取到最便宜的先全部买掉，这肯定是最优的，然后如果发现当前状态下只要有一个是最优的了，就没必要逐个一个一个买了，因为把当前最优的留到后面去买是完全没必要的，所以只要发现了之后可以直接return。另外还有一个估价的设计，如果当前花费加上还没买的所有的去最优情况都超过了ans那么一定无贡献，也可以直接return。
还有一个优秀的优化，我们会考虑那些尚未取到最优解的情况一个一个买，事实上，我们只需要记一下这个商品以前有没有过只买一次的情况，如果有的话那么以后完全没必要再一次一次买，可以一口气把剩下的全买了，这个剪枝非常有效。
接着，我试着在进行各种常数优化的时候，我发现我只需要再加一个优化就可以更进一步（极其有效）。那就是邻接矩阵改成邻接表，搜索能有这么优秀已经很不错了啦，不过我的短小简练的程序变长了几倍。
搜索代码：
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 using namespace std; 14 typedef long long LL; 15 const int MAXN = 51; 16 int n,k,total,ecnt; 17 int next[100000],first[MAXN],to[100000]; 18 double mp[MAXN][MAXN],ans; 19 int pd[MAXN]; 20 double d[MAXN]; 21 bool ff[MAXN]; 22 struct node{ 23 int num; 24 double price; 25 }a[MAXN]; 26 27 inline int getint() 28 { 29 int w=0,q=0; char c=getchar(); 30 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 31 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w; 32 } 33 34 inline void dfs(int x,double cost){ 35 if(x>=total+1) { 36 if(cost<ans) ans=cost; 37 return ; 38 } 39 double gu=0;int dui[51]; int cnt=0; 40 for(int i=1;i<=n;i++) if(a[i].num!=0) dui[++cnt]=i,gu+=(double)d[i]*a[i].num; 41 if(cost+gu>=ans) return ;//对其他所有的进行估价，如果取到最优的情况都无法更新就不可能对答案有贡献 42 double now=1e20; bool use[51]; memset(use,0,sizeof(use)); 43 double pric[51]; double cun[51]; 44 45 int zong=0; double zong_ans=0; 46 47 for(int i=1;i<=cnt;i++) { 48 int u=dui[i]; 49 now=pric[u]=a[u].price; 50 for(int j=first[u];j;j=next[j]) if(pd[to[j]]!=0) now=min(now,mp[to[j]][u]); 51 pric[u]=now; 52 if(now==d[u]) { 53 use[u]=1; cun[u]=a[u].num; pd[u]+=a[u].num; a[u].num=0; 54 zong+=cun[u]; zong_ans+=cun[u]*d[u]; 55 } 56 } 57 if(zong!=0){//取到最优的先全部都买掉 58 dfs(x+zong,zong_ans+cost); 59 for(int i=1;i<=cnt;i++) { 60 int u=dui[i]; 61 if(use[u]) { 62 pd[u]-=cun[u]; a[u].num+=cun[u]; 63 } 64 } 65 return ;//可以return，因为最优的肯定要先买掉，不可能留到后面 66 } 67 68 for(int i=1;i<=cnt;i++) { 69 int u=dui[i]; 70 if(use[u]) continue; 71 now=pric[u]; 72 if(ff[u]){//之前买过一次了，那么以后都不需要一次一次买，可以一口气买完 73 cun[u]=a[u].num; pd[u]+=a[u].num; a[u].num=0; 74 dfs(x+cun[u],cost+cun[u]*now); 75 a[u].num+=cun[u]; pd[u]-=a[u].num; 76 } 77 else{ 78 a[u].num--; pd[u]++; ff[u]=1; 79 gu-=d[u]; if(cost+gu+now<ans) dfs(x+1,cost+now); 80 a[u].num++; pd[u]--; ff[u]=0; gu+=d[u]; 81 } 82 } 83 } 84 85 inline void work(){ 86 n=getint(); for(int i=1;i<=n;i++) scanf("%lf",&a[i].price),a[i].num=getint(),total+=a[i].num,ans+=a[i].price*a[i].num; 87 int x,y; double z; 88 k=getint();for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=1e20; 89 for(int i=1;i<=k;i++) { 90 x=getint(); y=getint(); scanf("%lf",&z); 91 next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x; 92 if(mp[x][y]!=0) mp[x][y]=min(mp[x][y],z); 93 else mp[x][y]=z; 94 } 95 for(int i=1;i<=n;i++) d[i]=a[i].price; 96 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[j].num!=0) d[i]=min(mp[j][i],d[i]); 97 dfs(1,0); 98 printf("%.2lf",ans); 99 }100 101 int main()102 {103 work();104 return 0;105 }
BZOJ4349 最小树形图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。