#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define max 501 struct node { int wi,li,hi; }; node doll[max]; bool map[max][max]; bool mark[max]; int link[max]; int n; int findpath(int u) //寻找增广路径 { int i; for(i=0;i<n;i++) { if(map[u][i] && !mark[i]) { mark[i]=1; if(link[i]==-1 || findpath(link[i])) { link[i]=u; return 1; } } } return 0; } void maxmatch() { int i; int res=0; for(i=0;i<n;i++) { memset(mark,false,sizeof(mark)); res += findpath(i); } cout<<n-res<<endl; } int main() { int i,j,k; while(cin>>n,n) { memset(map,false,sizeof(map)); memset(link,-1,sizeof(link)); for(i=0;i<n;i++) { cin>>doll[i].wi>>doll[i].li>>doll[i].hi; } for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(doll[i].wi>doll[j].wi && doll[i].li>doll[j].li && doll[i].hi>doll[j].hi) { map[i][j]=1; } } } maxmatch(); } return 0; }
题目 http://acm.hdu.edu.cn/showproblem.php?pid=4160