首页 > 代码库 > HDU 4160

HDU 4160

http://acm.hdu.edu.cn/showproblem.php?pid=4160

大娃娃可以套在小娃娃外面(各边严格小),问最后最少得到几个娃娃

题目中的娃娃可以看做点,嵌套关系可以看做有向的路径,这样发现这题就是一个裸的最小路径覆盖问题

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <cmath>using namespace std;struct node{    int s,t,nxt ; }e[100005] ;int k,m,n,head[505],cnt,match[505],vis[505] ;int find(int s){    for(int i=head[s] ;i!=-1 ;i=e[i].nxt)    {        int tt=e[i].t ;        if(!vis[tt])        {            vis[tt]=1 ;            if(match[tt]==-1 || find(match[tt]))            {                match[tt]=s ;                return 1 ;            }        }    }    return 0 ;}int max_match(){    int ans=0 ;    memset(match,-1,sizeof(match)) ;    for(int i=1 ;i<=n ;i++)    {        memset(vis,0,sizeof(vis)) ;        ans+=find(i);    }    return ans;}void add(int s,int t) {e[cnt].s=s ;e[cnt].t=t ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;}struct node1{    int w,l,h;}kk[505];void read_graph(){    memset(head,-1,sizeof(head)) ;    cnt=0 ;    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            if(i==j)continue;            if(kk[i].w<kk[j].w && kk[i].l<kk[j].l && kk[i].h<kk[j].h)                add(i,j);        }    }}int main(){    while(~scanf("%d",&n),n){        for(int i=1;i<=n;i++){            scanf("%d%d%d",&kk[i].w,&kk[i].l,&kk[i].h);        }        read_graph();        printf("%d\n",n-max_match());    }    return 0;}
View Code

 

HDU 4160