链接:
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; }