首页 > 代码库 > 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;}
HDU 4160
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。