（匹配）Dolls --HDU --4160

链接：

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

 

 

代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;#define N 550/// 匹配
struct node {int w, l, h;}a[N];int G[N][N], used[N], p[N], n;int cmp(node n1, node n2)
{if(n1.w!=n2.w)return n1.w > n2.w;if(n1.l!=n2.l)return n1.l > n2.l;return n1.h > n2.h;
}bool Find(int u)
{for(int i=1; i<=n; i++){if(!used[i] && G[u][i]){used[i] = 1;if(!p[i] || Find(p[i])){p[i] = u;return true;}}}return false;
}int main()
{while(scanf("%d", &n), n){int i, j;memset(a, 0, sizeof(a));memset(G, 0, sizeof(G));for(i=1; i<=n; i++)scanf("%d%d%d", &a[i].w, &a[i].l, &a[i].h);sort(a+1, a+n+1, cmp);for(i=1; i<=n; i++){for(j=1; j<i; j++){if(a[i].w<a[j].w && a[i].l<a[j].l && a[i].h<a[j].h)G[i][j]=1;}}int ans = 0;memset(p, 0, sizeof(p));for(i=1; i<=n; i++){memset(used, 0, sizeof(used));if(Find(i))ans++;}printf("%d\n", n-ans);}return 0;
}