题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4160

有n个长方体形的娃娃;当长宽高都小于另一个的时候可以放进去,每一个里面最多放一个,问最优的套法下,最后可以剩下多少个娃娃;

用n-最大匹配就行了;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 550
int n, vis[N], used[N], maps[N][N];
struct node
{
int x, y, z, dp;
}a[N];
int cmp(node p, node q)
{
if(p.x!=q.x)
return p.x < q.x;
else if(p.y!=q.y)
return p.y < q.y;
return p.z < q.z;
} bool Find(int u)
{
for(int i=; i<=n; i++)
{
if(!vis[i] && maps[u][i])
{
vis[i]=;
if(!used[i] || Find(used[i]))
{
used[i] = u;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d", &n),n)
{
memset(a, , sizeof(a));
memset(used, , sizeof(used));
memset(maps, , sizeof(maps));
for(int i=; i<=n; i++)
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
}
sort(a+, a+n+, cmp);
for(int i=; i<=n; i++)
{
for(int j=; j<i; j++)
{
if(a[j].x<a[i].x && a[j].y<a[i].y&&a[j].z<a[i].z)
{
maps[j][i] = ;
}
}
}
int ans=;
for(int i=; i<=n; i++)
{
memset(vis, , sizeof(vis));
if(Find(i))
ans++;
}
printf("%d\n", n-ans);
}
return ;
}
05-11 21:49