hdu4160 Dolls

hdu4160 Dolls

​​‎

Problem Description Do you remember the box of Matryoshka dolls last week? Adam just got another box of dolls from Matryona. This time, the dolls have different shapes and sizes: some are skinny, some are fat, and some look as though they were attened. Specifically, doll i can be represented by three numbers wi, li, and hi, denoting its width, length, and height. Doll i can fit inside another doll j if and only if wi < wj , li < lj , and hi < hj . That is, the dolls cannot be rotated when fitting one inside another. Of course, each doll may contain at most one doll right inside it. Your goal is to fit dolls inside each other so that you minimize the number of outermost dolls.

Input The input consists of multiple test cases. Each test case begins with a line with a single integer N, 1 ≤ N ≤ 500, denoting the number of Matryoshka dolls. Then follow N lines, each with three space-separated integers wi, li, and hi (1 ≤ wi; li; hi ≤ 10,000) denoting the size of the ith doll. Input is followed by a single line with N = 0, which should not be processed.

Output For each test case, print out a single line with an integer denoting the minimum number of outermost dolls that can be obtained by optimally nesting the given dolls.

Sample Input 3 5 4 8 27 10 10 100 32 523 3 1 2 1 2 1 1 1 1 2 4 1 1 1 2 3 2 3 2 2 4 4 4 0

Sample Output 1 3 2

Source The 2011 Syrian Collegiate Programming Contest 最小路径覆盖问题 从源向每个节点的出点建边权为1的边 （因为只能做一回出点和入点）然后每个节点的的入点向汇建容量为1边 如果一个娃娃能覆盖另一个则从出点向入点建容量为1的边 然后跑dinic 即求出了最大匹配 初始的时候我认为我所有娃娃都得摆在外面 如果可以嵌套就就证明 这两个我可以变成一个 一个匹配我可以把两个点之间用一条边覆盖 就给连起来了 所以最后用总节点数-最大匹配即可

#include#include#include#include#define N 1100#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int x,y,z,next;}data[N*N*3];int num=1,h[N],w[N],l[N],level[N],hh[N],T,n;inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[num].x=x; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;data[num].x=y;}inline bool bfs(){ queueq;memset(level,0,sizeof(level));level[0]=1;q.push(0); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if (y==T) return 1; } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}int main(){ freopen("hdu4160.in","r",stdin); while(1){ n=read();if (!n) return 0;num=1;memset(h,0,sizeof(h));T=2*n+1; for (int i=1;i<=n;++i) l[i]=read(),w[i]=read(),hh[i]=read(); for (int i=1;i<=n;++i) insert1(0,i,1),insert1(i+n,T,1); for (int i=1;i<=n;++i){ for (int j=1;j<=n;++j){ if (i==j) continue; if (l[i]<=l[j]||w[i]<=w[j]||hh[i]<=hh[j]) continue; insert1(i,j+n,1); } }int ans=0; // for (int i=2;i<=num;++i) printf("%d %d %d\n",data[i].x,data[i].y,data[i].z); while(bfs()) ans+=dfs(0,inf); //for (int i=2;i<=num;++i) printf("%d %d %d\n",data[i].x,data[i].y,data[i].z); printf("%d\n",n-ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。