Dolls
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1288 Accepted Submission(s): 617
Problem Description
Do you remember the box of Matryoshka dolls last week? Adam just got another box of dolls from Matryona. This time, the dolls have different shapes and sizes: some are skinny, some are fat, and some look as though they were attened. Specifically, doll i can
be represented by three numbers wi, li, and hi, denoting its width, length, and height. Doll i can fit inside another doll j if and only if wi < wj , li < lj , and hi < hj .
That is, the dolls cannot be rotated when fitting one inside another. Of course, each doll may contain at most one doll right inside it. Your goal is to fit dolls inside each other so that you minimize the number of outermost dolls.
Input
The input consists of multiple test cases. Each test case begins with a line with a single integer N, 1 ≤ N ≤ 500, denoting the number of Matryoshka dolls. Then follow N lines, each with three space-separated integers wi, li, and hi (1 ≤ wi; li; hi ≤ 10,000)
denoting the size of the ith doll. Input is followed by a single line with N = 0, which should not be processed.
Output
For each test case, print out a single line with an integer denoting the minimum number of outermost dolls that can be obtained by optimally nesting the given dolls.
Sample Input
3
5 4 8
27 10 10
100 32 523
3
1 2 1
2 1 1
1 1 2
4
1 1 1
2 3 2
3 2 2
4 4 4
0
Sample Output
1
3
2
//将三个值分别看成一个点 变成一个二分图 如果a点包含b点 则连接
//这题我没看出是最小路径覆盖 只知道是 ans=总的点数-最大匹配
#include <stdio.h>
#include <string.h>
const int N=510;
int n,ma[N][N];
bool vis[N];
int link[N];
struct Node
{
int a,b,c;
}p[N];
bool Find(int x)
{
for(int i=1;i<=n;i++)
{
if(!vis[i]&&ma[x][i])
{
vis[i]=1;
if(link[i]==-1||Find(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
memset(ma,0,sizeof(ma));
memset(link,-1,sizeof(link));
for(int i=1;i<=n;i++)
scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
if(p[i].a>p[k].a&&p[i].b>p[k].b&&p[i].c>p[k].c)
ma[i][k]=1;
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(Find(i))
ans++;
}
printf("%d\n",n-ans);
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
HDU 4160
原文：http://blog.csdn.net/a73265/article/details/47379469
