首页 > 代码库 > 51nod 1392 装盒子
51nod 1392 装盒子
有n个长方形盒子，第i个长度为Li，宽度为Wi，我们需要把他们套放。注意一个盒子只可以套入长和宽分别不小于它的盒子，并且一个盒子里最多只能直接装入另外一个盒子 （但是可以不断嵌套），例如1 * 1 可以套入2 * 1，而2 * 1再套入2 * 2。套入之后盒子占地面积是最外面盒子的占地面积。给定N个盒子大小，求最终最小的总占地面积。
Input
第一行一个数N表示盒子的个数。接下来N行，每行两个正整数，表示每个盒子的长度和宽度。所有整数都是正的（N，以及盒子的长宽），且不超过200。Output
一行一个整数表示最终最小的占地面积。对于相同大小的盒子可以相互嵌套而只保留一个，考虑最大费用最大流，每个盒子i拆成a[i],b[i]两点，若x可放入y，则连边a[x]->b[y]，流量1，费用为x的面积，代表x放入y对答案的影响，源点到a[i]连边，流量1，费用0，使每个盒子最多只能放进一个盒子，a[i],b[i]到汇点连边，流量1，费用0，使每个盒子最多只能被放入一个盒子
#include<cstdio>#include<queue>#include<algorithm>int n;struct pos{ int a,b;}ps[207];bool operator<(pos a,pos b){ return a.a!=b.a?a.a<b.a:a.b<b.b;}bool operator==(pos a,pos b){ return a.a==b.a&&a.b==b.b;}const int N=400007,inf=0x3f3f3f3f;int es[N],enx[N],ev[N],ec[N],e0[N],ep=2,S,T,ans=0,l[N],in[N],pv[N],pe[N];std::queue<int>q;void adde(int a,int b,int f,int c){ es[ep]=b;enx[ep]=e0[a];ev[ep]=f;ec[ep]=c;e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];ev[ep]=0;ec[ep]=-c;e0[b]=ep++;}bool sp(){ for(int i=1;i<=T;++i)l[i]=-inf; l[S]=0; q.push(S); while(!q.empty()){ int w=q.front();q.pop(); in[w]=0; for(int i=e0[w];i;i=enx[i])if(ev[i]){ int u=es[i]; if(l[w]+ec[i]>l[u]){ l[u]=l[w]+ec[i]; pv[u]=w; pe[u]=i; if(!in[u])in[u]=1,q.push(u); } } } return l[T]>0;}void mcs(){ for(int w=T;w!=S;w=pv[w]){ int e=pe[w]; --ev[e]; ++ev[e^1]; } ans-=l[T];}int cs[2000];int main(){ scanf("%d",&n); for(int i=0;i<n;++i)scanf("%d%d",&ps[i].a,&ps[i].b); std::sort(ps,ps+n); n=std::unique(ps,ps+n)-ps; S=n*2+1;T=S+1; for(int i=0;i<n;++i){ ans+=ps[i].a*ps[i].b; for(int j=0;j<n;j++)if(i!=j&&ps[i].a<=ps[j].a&&ps[i].b<=ps[j].b){ adde(i+1,n+j+1,1,ps[i].a*ps[i].b); } adde(S,i+1,1,0); adde(n+i+1,T,1,0); adde(i+1,T,1,0); } while(sp())mcs(); printf("%d",ans); return 0;}
51nod 1392 装盒子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。